How do I measure the RPM of a wheel?
Using a hall effect sensor as Starliner suggested will be one way to interface with the wheel. Achim and Shutterdrone's suggestion to use a reed switch makes more sense though, given the supporting hardware a hall effect sensor requires to get a clean digital signal.

You might be able to pickup a magnet and sensor from a broken bicycle computer but if you can't, a local component store should have one of each in stock. The advantage of a recycled sensor and magnet is the you will already have the mounting hardware.

There is a page on the arduino wiki on ReadingRPM signals. To calculate the speed multiply the RPM value by the circumference of the wheel (2 * pi * radius [in meters]). The result will be in meters per minute.

Edit: I've notice that the linked code is for systems with two pulses per revolution. One magnet is sufficient for your task. Additionally, for a bicycle computer you'll probably want the result to be in KPH (or MPH if you live somewhere that still thinks that's civilised). I've made some (untested) mods to the code on the wiki to print out KPH and pasted them bellow.

volatile byte revolutions;

unsigned int rpmilli;
float speed;


unsigned long timeold;

void setup()
{
  Serial.begin(9600);
  attachInterrupt(0, rpm_fun, RISING);

  revolutions = 0;
  rpmilli = 0;
  timeold = 0;
}

void loop()
{
  if (revolutions &gt;= 20) { 
    //Update RPM every 20 counts, increase this for better RPM resolution,
    //decrease for faster update

    // calculate the revolutions per milli(second)
    **rpmilli = (millis() - timeold)/revolutions;** EDIT: it should be revolutions/(millis()-timeold)

    timeold = millis();
    **rpmcount = 0;** (EDIT: revolutions = 0;)

    // WHEELCIRC = 2 * PI * radius (in meters)
    // speed = rpmilli * WHEELCIRC * "milliseconds per hour" / "meters per kilometer"

    // simplify the equation to reduce the number of floating point operations
    // speed = rpmilli * WHEELCIRC * 3600000 / 1000
    // speed = rpmilli * WHEELCIRC * 3600

    speed = rpmilli * WHEELCIRC * 3600;

    Serial.print("RPM:");
    Serial.print(rpmilli * 60000,DEC);
    Serial.print(" Speed:");
    Serial.print(speed,DEC);
    Serial.println(" kph");
  }
}

void rpm_fun()
{
  revolutions++;
}


Also, I've enabled 'community wiki' on this, which I think means other users can edit it. If my maths is wrong (and you can prove it!) jump in and fix it for me. :)