It is easy enough to use a very basic 5V "wall wart" type power supply as a mains voltage detector. Connect the 5V to an Arduino digital input pin. When the 5V disappears, that means the the power mains have failed.
Do you mean "when the power is coming back"? Or do you mean "when the power comes back"? The first would involve using a crystal ball to predict the future. The second would be simple to do so that it sends out a message upon power=up. If you had an RTC (Real-Time Clock) in the system somewhere, you could even keep track of how long the power had been out.