Is there a way to save state in a very low power way?
System power is disconnected and then reapplied, the ATmega will start from the reset vector, as usual (due to the power-on reset). 

So you can perform your inizialization routines in the very first part of your main() function.

When you finished doing your periodic measurements, do not remove power to the ATmega. Instead, put it in power-down or power-save mode through the sleep instruction.



This will draw less than \$1 \mu A\$ @25°C. When the wakeup interrupt occurs (e.g. timer expiration, external pin etc.), the interrupt will be executed and the program will restart from the instruction that follows sleep. In this way you can avoid any external hardware.