Switching Arduino/ATMega to sleep mode when on battery
Diode or-ring is right but here's a slight improvement for the hardware: -



When the 5V voltage is present it turns off both P channel MOSFETs and power is routed thru the schottky diode to the MCU. The MCU's input "knows" that is is connected to the 5V rail and this is important for your watchdog timer.

When the 5V disappears, the MOSFETs gate voltage falls to 0V/Ground and MOSFETs turn-on and apply 3V (with barely any voltage drop) to replace the 5V (which isn't there any more). You want minimum volt-drop on this power rail to keep the MCU running for longer when the 3V battery starts to fail.

Again, the MCU can detect that it should be using its watchdog because the IO pin is low. The 10k in series with the input is to offer over-current protection when the 5V supply is active and the power voltage reaching the chip may be somewhat less at 4.6V (due to the schottky diode).

It should be noted that the right-hand MOSFET is probably not needed in this application - I took the idea from a circuit that also protects against reverse polarity on the 3V input.

Software side - sorry, this answer is ineligible for bonus points.