A relay is a simple switch controlled by an electromagnet coil. The "NO" (normally open) side is off until you apply power to the coil. The "NC" (Normally closed) side is on until you supply power to the coil, at which point it turns off. Switches don't have polarity. If you connect the common into one part of a circuit and the "NO" side into the other, it doesn't matter which goes where.
Edit:
As another poster pointed out, you should wire the relay so it switches the hot leg from the plug, not the neutral (Assuming you're in the US or another country with polarized plugs.) That is much safer, since it means when the relay is off, the lamp is only connected to the neutral line. If, instead, you wire the relay to switch the neutral leg then the lamp will ALWAYS be connected to hot, and if somebody touches the wires they could get a shock.
Important:
What does matter is how you power the relay. If you try to drive a simple relay directly from a logic pin, it will likely damage or destroy the Arduino.
If you're using a "digital" relay that takes a constant 5V source, and a logic level control, such relays have built in transistors and protection diodes that prevent the relay coil from destroying solid state electronics.
If you're using a simple relay, you'll need an appropriate transistor to boost the current to the coil, as well as a "flyback diode" to protect the transistor from back-EMF when the coil is disconnected.