Knowing speed is actually harder than any one has made it out to be.
Shaft encoders are limited by the slip of the wheels. (They tell you how fast you SHOULD be going, not how fast you are going)
Accelerometers are limited by the huge amounts of noise they generate. If you want a cheap accelerometer... Analog devices makes some 5v ones that will plug right into an analog input on the RC.
ADI iMems Sensor
Keep in mind that an accelerometer isn't at all useful if you hit something. Additionally you have to integrate them to get velocity.
What you really need is an external reference. Something like using the camera on an orthogonal plane to your plane of motion to compute differences in the images and compute distance based on the shift.
In general this is a very nontrivial problem and is something I'm working on as a Master's Thesis in Computer Engineering.
That doesn't mean you can't fudge it a little bit.
Hope that helps.