Building a back-up battery for your Arduino just takes a little bit of soldering! Take a look at the following circuit.
This is how the circuit works: Parallel circuits always have equal voltages (Kirchoff's Voltage Law); but when you have two parallel voltages, you can't push a high voltage down so you must push the low voltage up! Our battery wouldn't appreciate that very much though, so we've adding some diodes in series of each voltage source. This means that the voltage supplied to the Arduino will be the maximum of the two voltage sources.
If you have a 9V wall wart which tends to supply roughly 9.2V and a 9V battery which tends to supply 9V or less, then only the wall wart will be drawn on (well mostly at least...)
What we're going to do is solder two barrel jacks into your protoboard. It will have the normal power supply and the back-up battery plugged into it, and will plug into the Arduino itself. Here's a step-by-step guide on how to build a back-up battery for your Arduino.
Bill of Materials
Step-By-Step