nanogru is right, you will need definatley need an IMU, not just an accelerometer. The one he recommended looks pretty good.
Would also recommend going down the Ardiuno track, it will make life much easier and cheaper.
I normally use encoders too. There is a good Arduino library for encoders:
Have had good success with optical quadrature encoders. Can be read using digital or interrupt inputs. If you want the best performance, you will want to use at least a Mega to have enough interrupts.
You could also upgrade your robot with a laptop, Kinect, Linux, and ROS (if your robot can handle the payload).
This stuff is pretty easy to set up these days for 6DOF SLAM and autonomous navigation, especially with new tools like MoveIt:
What do you plan on doing with the position data? Is it for autonomous navigation?