Do a search for a K1010 (available from RS). Put a 1N4007 across it (in reverse to clamp the negative cycle because the reverse voltage will almost certainly exceed the opto's max rating and you're in danger of blowing it up). Feed that with a 270K Resistor (mains rated... the CR25 types are marginal here - unless you use say 2 x 150K - one in each input leg). Use a PIC pin with a pull-up (internal weak pull-ups are just fine) and set your software to detect the 50/60Hz AC pulses (no pulses - no mains).

PS... just in case anyone reading this is in a part of the world where they have toy voltages coming out of the wall, the above is good for 220-240vAC.