I have recently been designing an Arduino-based system to deal with automatic garden watering and related tasks. I decided that protecting against power failures was pretty important, given that the controller may be doing things such as switching on water supplies, etc.
So, I decided to build a circuit that would act as a mini 'UPS' for the Arduino, automatically switching over to battery backup and allowing for a graceful shutdown to conserve battery power. With this design, the Arduino can poll the input voltage and source, and when it is on batteries it can switch itself off (it comes back on if the AC power is restored).
I am pretty new at doing stuff on the hardware side, but my completed circuit works great and I figured I should share it, since there seems to be some interest in backup controllers in this community.
Many of the parts used were ones I either had around somewhere, or was able to get out of old appliances 
Operation:
-When the 'wall' supply is on, no power is drawn from the batteries. When the wall supply cuts out, some big caps power the Arduino while the source select relay switches to the batteries. When power is restored, the source is switched back to wall power and the Arduino is started up if it had been shut down.
-The Arduino can poll the current input voltage and source (wall or batteries). During normal operation the shutdown select pin should be set high. When the program detects that a power failure has occurred and batteries are being used, it finishes all current tasks, writes the state to the eeprom, and then sets the shutdown select pin low. This disconnects power from the batteries and turns off the Arduino until the power is restored.
-Optionally, the Arduino can instead continue to operate on battery power and monitor the battery voltage, then shutdown when the batteries are depleted.
Notes:
-The voltage regulators I used are KA78L05A. I used 5v relays so that I wouldn't have to pick through the parts bin to make a voltage divider for the source detect pin.
-The zener diode was my solution to relatively large capacitance in the wall-wart. Without it, when power was lost, the wall-wart cap was holding the relay on longer than the output cap could power the Arduino/servos.
-The voltage divider for the source voltage detect pin was chosen by the contents of my parts bin and an approximate maximum input voltage of 14v.