Hall effect sensors and reed switches are the most mentioned here, and they're the best solution. 

The **reed switch** will be cheaper, but may give you false pulses when the bike gets a shock. If that's just one from riding of the curb the software may easily filter it out, but it's different when you're riding over cobblestones, which may give you false pulses all the time. More shock resistant reed switches will require a stringer magnetic filed to activate, but a Neodymium magnet will fix that.

**edit** in answer to m.Alin's questions  
Reed switches are fast. That's because the reed has a low mass (= low inertia) and a low travel, often only a few tenths of a mm. [This reed switch](http://www.meder.com/fileadmin/meder/pdf/en/Products/Reed_Switches/Reed_Switch_1A80.pdf) has an operate time of < 0.6 ms, and a release time of < 0.1 ms. At 36 km/h the switch travels 5 mm in 1 ms when mounted halfway the wheel's diameter. So it's fast enough to be activated when it passes the magnet.  
[This document](http://www.meder.com/fileadmin/meder/pdf/en/Reed-switch_Life_Test_Data.pdf) about the same switch gives a life expectancy of > 10\$^7\$ operations, and that's not as much as it seems. If you would do 25 km a day you reach that 10\$^7\$ switch events in 2 years.  
*end of edit*  

The **Hall effect switch** doesn't have these disadvantages, but is somewhat more expensive.

<br />

You get time \$T\$ between 2 pulses as information from the sensor. Then

> speed \$ v = \dfrac{\pi D}{T} \$

in m/s if wheel diameter \$D\$ is expressed in meters, and \$T\$ in seconds. Convert to km/h by dividing by 3.6, divide by 5.79 for mph.

> distance \$ s = \text{pulse count} \times \pi \times D \$

in meters if wheel diameter \$D\$ is expressed in meters. Divide by 1000 for distance in km, by 1609 for miles.