I think this could be done with your serial port, rather than using a relay on the actual power switch.
Check out the "Coffee Maker HOWTO" at www.tldp.org
They outline how to turn a switch on and off with linux and your serial port, for a coffee maker.
You could glean some information to use the serial port to pickup the presense of voltage, and run a script when the status changes, including a shutdown command. Turning it on would be aproblem, though.