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.
With no patterns one could think of a situation where the surface sand/terrain would be displaced but your actual position was exactly the same.