I don't care how much it's moving, how fast or in what direction, I just want my Arduino-based project to know if it is moving or not (so I can shut off high-current drain LEDs when my bike is stationary to save my battery.)
Do I want an accelerometer, gyroscope or some other kind of sensor?
If it's for use on a bicycle then I'd use a low-power opto detection circuit on the spokes of the wheel. There are several variants of this and of importance is the ability to pulse the LED to conserve power thus, if a spoke passes by at 10 times a second (indicating a minimum speed) then you'll need to power the LED for at least 0.1 seconds and "look" for a beam interruption - this indicates movement. Just an idea.
You might also consider a saddle switch so that if someone is not sat on the saddle and no movement is detected then the LED shuts down completely.
An accelerometer would be suitable in most cases. Technically acceleration will be 0 at a constant speed, but in practice unless your project is mounted on some sort of exceptionally low vibration rail you'll see fluctuating accelerations during movement. It should be fairly simple to use a rolling average in each axis and consider the device as "moving" when the variation is above a certain threshold. There will be a little bit of random acceleration detected when the device is stationary, but thresholding should deal with that.
You can get boards with I2C accelerometers mounted on them from a lot of hobbyist electronic suppliers. The procedure for talking to them will vary slightly depending on the chip, but generally talking to I2C devices from an arduino is fairly easy.
While you specify 'seeing if it's moving' as your goal. I might recommend a different measure of checking if the bike is in motion. The amount of noise accelerometers capture is astonishing - it could be that your situation is such that there will be a clear delineation between 'in use and moving' and 'not in user and still moving(slightly)'. I would not expect that to be the case though.
It's worth considering that if the bike is attached to/parked in a structure that moves often(others attached or detaching their bikes, trains or vehicles close by, indoors near a crazy HVAC pump, indoors on wood/bouncy floors when someone walks by...) then your lights will come on whenever the bike moves. This isn't really what you want. You want the lights to come on when a rider(you) is moving the bike. To that end a proximity sensor(which is blocked only when you are on the bike) or even something like a speed sensor/reed switch would work. Here is a tutorial for an Arduino bike speedometer using a reed switch: http://www.instructables.com/id/Arduino-Bike-Speedometer/ The bonus of this is you get a speed reading and it would be fairly trivial to add a trigger for the lights(with a delayed turn off for periods when the bike is not moving for lights/traffic and similar.)
Accelerometers as others have suggested are pretty easy to use especially on an Arduino with all the libraries and breakout boards available. Another thing that might worth looking at is a Piezo Vibration Sensor like this one avaiable from Sparkfun for $2.95 at the moment:
Just be careful to note how high the voltage output can be, they suggest using a resistor divider to reduce the voltage and using an ADC pin. While I'm not that keen personally on using the internal diode clamps in an AVR if you used say a 1K series current limit resistor given the low current to start with I can't see you'd have too many problems connecting to a digital input if that gives enough sensitivity and the slight rise in Vcc won't cause other problems until the clamps take effect.
Anyway it might be another sensor that would be interesting to take a look at. While it probably won't matter a lot for an Arduino that has relatively high quiescent current on the regulator and your particular project they can be neat for a lot of projects. They draw zero power and can be used to wake up a microcontroller from deep sleep assuming you get enough vibration to trigger a logic high level.
Some kind of a low-resolution high speed camera and optics that takes many photos (at hundreds or thousands of frames per second) of the surface it is moving on, and compares them in real time with a built-in purpose-built processor to measure motion. Preferably all on a chip, with a convenient MCU interface.
In other words, an optical mouse sensor.
Unfortunately, it looks like the Avago parts are no longer stocked in distribution, but you could hack an optical mouse, which will give you the optics and the illumination LED as well (you may have to modify the optics to get an appropriate distance). Many of the sensors appear to be from Pixart in Taiwan, and the datasheets are available (often not true).
A lot of these responses are overcomplicated and will most likely result in false positives and/or false negatives. Accelerometers will go off if the bike is moved at all, and will not fire if you're moving at a constant rate. Taking optical footage of the ground is process-expensive and not incredibly reliable if the sensor isn't that great. Measuring vibration will fire if somebody bumps your bike or it's shaken in any way.
There's a very simple question you must ask to find the correct answer: What is different between a rider riding the bike, and something else moving it? The answer is equally simple: the wheels spin.
So your solution, then, is to use something that measures the wheel at the axis of rotation, something like Spehro's mouse idea, perhaps.
This will ensure that your system fires if and only if a rider is causing it to move.
Or you could sense when a rider is on the bike, such as:
If you don't care what sort of movement happens, then a rolling ball switch is the easiest solution to implement. It requires just a digital input and a low pass filter.
One example is the Signalquest SQ-SEN-200. There are other smaller and bigger variants of the same technology (SMD and through hole).
To just detect that the object is moving I suggest a photointerrupter with a pendulum of some sort. Take one like this and build a "mechanical thing" that moves in its detection area. http://se.farnell.com/sharp/gp1s53vj000f/photointerrupter-compact/dp/9708065
You could probably salvage all the needed parts from a computer mouse with a wheel button or ball movement detector.
