[BitTwiddler]

Team 1726 has used both kinds of magnetic sensors with good results.
The gear tooth sensor will detect the presence of ferromagnetic material (such as a steel sprocket) passing by whereas the magnetic switch will require a magnet (North turns it on - South turns it off).
The magnetic switch will require some additional components but the gear tooth sensor is ready to use with a Digital IO.
The magnetic switch is a lot cheaper to purchase and is also available at Sparkfun Electronics.
Also, we found the output of the magnetic switch to be somewhat noisy electrically but using the Low Pass filter from the PID library can reduce the noise.