I did some practical experimentation related to writing data when disconnecting power. With a 680uF cap, a 12v supply, and an Arduino + sensors drawing 40mA, I get 100ms to save data after I detect power loss: plenty of time to write and exit.
I have an Arduino Pro mini 3.3v, GPS, and micro-SD card, which together draw 42mA. With a 680uF capacitor connected across the battery supply line (3x NiMH AA, 3.8v), and the main loop checking in every 20ms, I get only about 20ms warning before shutdown. That is, I can write one record to my uSD card saying 'looks like input voltage is dropping', but only one before shutdown. However with a 12v supply, I get a good 100ms warning; and if I increase to 1800uF I get 300-400ms at 12v, 250-300ms at 9v, and 40ms (two chances to notice in my setup) at 3.8v.
Detailed data. (I harvested capacitors from a discarded laptop power brick.)
This is one of the top hits for saving Arduino data on power-off, and has lots of useful advice and theoretical background; hopefully some empirical numbers will benefit other people.