"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:
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.
