I just built up a few (9, still need to buy some parts for the 10th) Mega Lithium Backpacks, which are little battery shields that snap to the back of the Arduino Mega and give it battery power.
Here are some pictures...
It's the same form factor as teh Arduino Mega, and it connects and stays in place using standoffs on the back...
Here's a picture of the extended power and power test rails... I put at 5 volt and 3.3 volt power line on the back. The 3.3 volt rail is mostly because all of sparkfun's stuff seems to be 3.3 volt, while the arduino team seems to stick to 5 volts. The top rail is the power test, which if it's plugged into an analog input port, will tell you how much power the battery has left in its charge:
Anyway, I'm definitely proud of soldering and testing 9 of these by hand tonight...! I put them up on the liquidware shop and put up some more pictures on flickr over here... inthebitz | Flickr