Use a rectifier (1N4004) and a 10K 2W resistor in series with the LED side of an optoisolator. Put another rectifier across the LED in the reverse direction to protect it against reverse voltage. Connect these across the power line. Put a 10K resistor on the collector of the phototransistor to 5V. The output will be an isolated 50 or 60 Hz square wave.

I would use an interrupt to "watch" this, so your PIC could do other things while watching the power line. Of course the output of the phototransistor will only be LOW for each half-cycle, so if you sampled the phototransistor every 5 ms or so, and it never went low, it would be an idication that the power was "gone'. Note that the rising and falling edges of the square wave will be very close to the zero-crossings of the power line.