The simplest magnetic sensors would be a reed switch, a small flap of metal that either opens or closes a switch in the presence of a magnetic field. There are also Hall Effect sensors which actually produce an analog voltage but can be used in a similar way by establishing a threshold voltage in the sketch.
Edit: Also does your motorcycle currently have a standard speedometer? Depending on what the output signal is, you might be able to connect the Arduino to it instead of making a seperate sensor.