Adafruit to the rescue as I am pushing my project to be portable.
One lithium ion polymer battery and an Adafruit PowerBoost 500 Charger later I was able to get the project untethered from a power source.
Will figure out battery life and such in the near future.
Couple of interesting notes: I already went the alkaline battery route – it worked to a point but the are too bulky for my applications and they had about a 4 hour life span. The combination of Adafruits PowerBoost 500 Charger and the LiPo seems to be (so far) ideal.
The PowerBoost 500 does not work for this application (probably no application) if you connect it via the 2.1mm Power Jack. The Power Jack needs at least 6V to operate properly. I have not yet evaluated using the USB power input. My initial finding showed that it did not work but I am a bit skeptical about my USB connection. Does not really matter much as I know have the PowerBoost 500 connected right to GND and VIN which works great!
Further reading on the subject it appears the only way to power the Arduino from the PowerBoost 500 is the way I ended up doing it — straight to GND and VIN. Makes sense as the USB optional output appears to be for charging other units, not powering a device.