Detect sudden change in current and send signal to arduino
You need to think about the range of power you expect (when device is 'on'. If it's not orders of magnitude, them you can
Use a current transformer to sense current, then a rectifier, filter, signal conditioning to get average or peak value which can be fed to the ADC. 

There are also single chip solutions which will give you all the data over a serial line (see MAXQ314, for example).