I used this rechargeable battery to power the Arduino GPS.
Duracell Instant USB Charger with Lithium ion battery / includes universal cable with USB and mini USB
Monoprice.com is a crazy cheap place to buy cables. I needed a short USB cable to connect the Arduino to the rechargeable battery with a USB plug. The USB cables at best buy were $25.00 and up! At Target they were $15. At monoprice the cables were $0.84 plus $2.24 to ship. I got a cord to charge my cell phone while I was at it. All for $4.24.