All true. JPL has been a world leader in development of visual odometry ("VO"), which is key to estimating slip, which in turn is key to not getting stuck in sand.

The method hinges on establishing correspondence between visual features in before/after images. Then, since you know (through stereo ranging) how far away things are in both images, you can match points and see how far you've gone. This works better the more visual features (tiny edges and corners) you have to cue off of, and presumably these treads are generating more distinguishable features. They ran VO on Spirit and Opportunity, and they will on Curiousity as well.

A summary is in the first page of this little white paper:

http://www.lpi.usra.edu/meetings/marsconcepts2012/pdf/4053.p...

and one full description is here:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.104....

The good thing is that VO requires no extra hardware, because you already have stereo cameras.

By the way, they do make commercial velocity sensors of the kind described in the GP comment (special camera looking down):

http://www.corrsys-datron.com/optical_sensors.htm

These may not use VO, they might just use optical correlation. Sometimes they're used in robotics.