You didn't say which Arduino you are using, these instructions are based on an Arduino Uno, but should work for most if not all Arduinos.
Connect a 9v battery to the Vin pin of the Arduino through two 1N4001 diodes or similar. The PWRIN jack is already connected to VIN via a diode, so the two diodes will provide isolation between the two, and the 9v battery should not draw any current when the main power is supplied since its voltage will be slightly less because of the two diodes.
Passerby helpfully supplied a schematic of this approach:
simulate this circuit – Schematic created using CircuitLab
Another option would be to connect a P-channel MOSFET in series with the battery voltage, instead of the diode, and connect the gate to the PWRIN jack. When the main power goes out, the gate will go to ground turning on the MOSFET. This solution avoids the extra voltage drop of the two diodes, which is not a factor in this case since the Arduino should work fine with 7.5V or so on its input, but may be a factor in other applications.
The Arduino takes about 50 mA with no load, so a typical 9v battery, with a capacity of 500 mAh, should last may be 8 hours. The maximum leakage current of the MOSFET is 100 µA at room temperature. If the battery voltage started out higher than the power in voltage minus the diode drop (9V - 0.7V), then the battery could lose some power until the battery dropped below 8.3V, but at this point the battery should not lose any more power.