"Practical Arduino book" has a very interesting circuit for this purpose: http://www.practicalarduino.com/projects/vehicle-telemetry-platform
Here is how I've recreated it:
http://25.media.tumblr.com/8c2d23c56eb465d055e4d8c8406017c8/tumblr_mjb5327Gzh1s6jcaao1_1280.png
It uses LM2940CT and huge electrolytic cap - even if supply voltage drops, you'll have about a second to shut down your Arduino gracefully (close files on SD properly, and so on).
"Arduino Cookbook" (2nd ed.) has a chapter with examples on how to reduce Arduino's power consumption to absolute minimum - have a look at it, too.