It depends on how small a power failure you want to look for. The wall wart idea is a really good one, but you have to test the actual wall wart to see how long its filtering capacitor can sustain a charge before dropping out. The more current you suck out of the wall wart, the faster it will drop to a logic zero. There are other things you can do like actually measuring the wall voltage using an analog pin on the arduino and such, but they carry inherent risks.
So, if you want to do somthing like that, get one of the AC wall warts. Take a look around, you may already have one. These wall warts supply AC power to the device, not DC and are usually in the 12V range. With one of these in hand, you can make a voltage divider to drop the voltage down to a level the arduino analog pin can read and then sample it rapidly to see what the voltage is for a given instant. You'll have to allow for the zero crossing, but that's not too hard. You can also rectify and filter it just slightly and feed it through a voltage divider to a digital pin. Your choice.