Portable Arduino Battery

Need a portable battery for my project with the gsm shield. I'm thinking about either using a bunch of cheap store bought batterys in a holder or a single expensive rechargeable battery.

A. What is the ideal type and number of run of the mill batteries and holder I could use?

B. What is a good single rechargeable battery? I assume it will be 3-2.5A or greater and around 9V although some people claim 9V are bad and will burn out the arduino. Preferably rechargeable and pack of cards size or smaller. All I can find searching are chargers. What batteries do you guys use?

PS A project I'm looking at uses this battery

but its only 3.7 volts? How does something with this low voltage power the arduino if its below the recommendations?