In a nutshell, you add a high-frequency, low amplitude signal to the low-frequency, high amplitude AC signal. Powered devices don't care about the added noise, and filtering can extract the high frequency signal without the low frequency component.
Probably due to the dangerous nature of mains power, I haven't seen any blogs or tech notes on how to implement it. However, an Amazon search for "Power Line Communication" yields 325 books, of which most appear pertinent to your question, and by much more qualified persons than myself.
It is possible. However, if you're using an Arduino, you likely don't have the expertise to create a well-isolated and well-insulated shield. No offense intended, I would be hesitant to try it myself, and I've had some training on the topic at a university. Also, an Arduino is meant to be handled, and, as Joby pointed out, it will definitely need a well-designed enclosure.
All things considered, you'll have a much more flexible, easier to create, cheaper, and more robust system if you simply use an Ethernet shield and buy a powerline ethernet adapter like the one you linked to. Do some searching, they're available for less than $30.
Slightly off-topic, but I would consider Power over Ethernet to be much more within the reach of an Arduino shield. National has a decent appnote/FAQ on their LM507X series of powered device controllers. This is something I'd like to try once I get some free time....
Have you considered looking at the other end of the spectrum? Low-frequency communications, as you have rightly noticed, are not as common as they used to be.
There are many chips around that handle all the modulation, demodulation, etc at >1GHz - take the MRF24J40MC from Microchip (maybe not the cheapest solution) for example - 2.405Ghz to 2.475GHz. Or the ADF7241 from Analog Devices - again in the 2.4GHz range. There are many many more.
Yes, I know these are aimed at wireless communications, but then, what is Cable TV if not wireless communication with no aerial? The cable is basically a closed loop aerial between two points. A modulated high frequency signal being sent between two points through a medium - just using copper instead of air.
Best Answer
Have you looked into the Dallas 1-Wire protocol? It is really low speed and if you device takes relatively little current then you can get away with using parasitic power and power the device with the data lines.