In a battery powered project I'd always go for a way to feed the arduino directly with regulated 5V. The voltage regulator has a pretty bad efficiency.
A switching regulator is the way to go when you don't want to use your precious battery power to heat your arduino.
[edit]
BTW: A cheap way to get a 5V power source are the USB power packs you can buy to charge your phone/mp3player on the go. They contain a lithium battery, a 5V step up regulator and a charging circuit. You can get them for about 10$
[/edit]