What is it?
It is a special mode in which an android phone or tablet can be booted, in order to reset, restore, root or update it.
How do I boot my Android device into Recovery Mode?
An Android device is usually booted into recovery mode by using certain hardware key combinations during powering it on. For example, a Samsung Galaxy Y Duos (GT-S6102) can be booted into recovery by powering it off, and then powering it on while holding Volume Up + Home + Power buttons.
http://www.controlf.net/recovery/ seems to list out the combination for quiet a few devices. Add your own in the comments
Point to note
This is a very powerful feature of android devices. But it is also a vulnerability. For example, a person stealing your phone can just boot into Recovery Mode and factory reset your phone.
I'm afraid of the black screen and serious-sounding options. What do I do?
Remove your battery. Put it back on. Power on your device. Forget this post. All this in good humor :P
What is the 'reboot' option? Will it erase my phone?
The 'reboot' option just powers off your device, and powers it on again - just the same thing as switching it off and on yourself.
Where do I go if I run into trouble?
The best place to look would be Google and the XDA Forums - http://forum.xda-developers.com/