A relais is a switch which can be triggered by a voltage (and current flowing). Most relais consist of an electromagnet which pulls or pushes on magnetic components in the relais. There are also electronic - so called solid state relais which don't have mechanical moving parts. This section is about the mechanical type of relais which has a coil.
You could also build your own relais out of a button which is pressed by a motor when voltage is connected to it.
Relais come in different voltage rating for their coil and also for the switch.
Input and Output Ratings
Input: Coil
Coils of a relays are limited to a certain voltage range which is necessary to work properly. Below that voltage the coil isn't strong enough - Above that voltage the coil is using more current and thus getting warm. For short moments it's also ok to use more voltage than specified.
There is no "standard voltage" for relais. Typically the voltages for the coils are specified between 5V and 230V.
On Microcontrollers it is useful to use relais with voltages which are available in the circuit. For example if you plan to only use the arduino board on USB power you have to use a relais which works with 5V (Many 6V relais work also on 5V - see the spec sheet of your relais or simply try it).
Output: Switch
The "outputs" of a relais are the terminals of one or several switches which act simultaneously when the voltage on the coil is applied. An often occurring misunderstanding for relais to prevent: There is no voltage a the Output terminals you can measure.
There are many different variants of switches built in in relais (for a list of common switches see the table on this wikipedia page - very common are relais which have 3 pins as switch contacts (a changeover switch). It consists of two switches - one of them opens when voltage to the relais is applied, the other closes when voltage is applied. Two of the switch's terminals are combined to one terminal - so there are not 4 separate terminals for the 2 switches but instead 3.
The relais switches are made for specific purposes. There are relais which are made for high currents, but they can't deal with high voltages (for example relais which are used in a car are made for 12V and often 10A or more) and there are also relais which are made for high voltages like up to 230V or even more - but for only 2A or less. A relais made for 230V also works on 12V - but you shouldn't try to use a 12V switch on a 230V circuit.
Relais are also often lablede with a "VA" rating like 500VA. This means the product of the voltage and the current may not exceed 500. However the current labled on the relais may not be exceeded as well. For example for a relais labled 500VA 2A you are only allowed to use 2A no matter what voltage you are using. Since there's no voltage labeled you have to calculate it on your own: 500VA / 2A = 250V (so this is the maximum voltage of the relais).
The most important selection criteria for the switches is the current they are designed for.
Using relais on Arduino (logic level outputs)
The coil of most relais can't be directly connected to a microcontroller's output as they don't have sufficient power (Arduino: 20mA and 5V per pin - most relais use at least 40mA and more). So amplification is necessary, for example using transistors or darlington-Arrays like ULN2003 or similar. Also since we are switching a coil it is necessary to add a freewheeling (flyback) diode to protect the circuit.
Links
Different schematics and explanation: logic level outputs and relais (German): http://www.mikrocontroller.net/articles/Relais_mit_Logik_ansteuern