Below are the features of the two modules.
I am thinking about powering this project with AA batteries but I am really unsure about the number of batteries to use and of course the efficiency
Quad-Band 850/ 900/ 1800/ 1900 MHz
GPRS multi-slot class 10/8
GPRS mobile station class B
Compliant to GSM phase 2/2+
Class 4 (2 W @850/ 900 MHz)
Class 1 (1 W @ 1800/1900MHz)
Control via AT commands (GSM 07.07 ,07.05 and SIMCOM enhanced AT Commands)
Low power consumption: 1.5mA(sleep mode)
Can be powered by arduino (5V) - Typical 5V and 50 mA
Operation temperature: -40°C to +85 °C
I use rechargeable NiMH AA-cells for my battery powered projects. They currently
come in 1800-2500 mA-hr capacities, and should run your items for many hours. You
will probably want at least 6 cells in series ~ 7.2V when fully-charged.
I currently have not done as much with battery operated devices, but I'm planning to. Rather than use AA batteries, I plan on using portable 5v batteries meant to charge cell phones. I bought the EZOPower 5000 (http://www.amazon.com/gp/product/B004I0H9MU/ref=oh_details_o02_s00_i00) from Amazon. It has two 5v 1amp ports that can be used to power separate devices. I like this because to charge it up, I only need a micro USB cable and a 5v wall socket that I can also use to charge my phone or my Nook, and not a separate AA charger. As a test, I ran my UNO doing blink off the EZOPower for about 3 days of continuous usage (no special power saving programs, just the standard blink program). I use cameras and flashes that take 2 or 4 AA batteries, but even so, I prefer the EZOPower because it is more convenient.
At some point, I'm probably going to have to go a similar battery that has separate ports for 5v, 9v, and 12v, since I want to use wireless video, and that primarily seems to be 12v.
The EZOPower happened to be the one I bought. At the time it was $20 but the price has gone up a little since then. There are other batteries with more capacity than 5000maH, if you need more capacity. As I mentioned, you can also get batteries with separate 5v, 9v, and 12v ports if you are going to be powering motors, etc.
For what I'm working on, I only need to power the unit for a single day, and I can recharge the battery at night for the next day via an A/C usb port. If you need much longer run time, you should check out Nick Gammon's article of how squeeze the most runtime out of your Arduino and Arduino clones: Gammon Forum : Electronics : Microprocessors : Power saving techniques for microprocessors