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....
FFT is overkill. Use the Goertzel algorithm to detect a single frequency.
This effectively implements a second-order IIR filter with poles at e + 2πiω and e − 2πiω, and requires only one multiplication (assuming 2cos(2πω) is pre-computed), one addition and one subtraction per input sample. For real inputs, these operations are real.
"My communication is very simple, if the frequency of the portant is present this is a 1, if not, is a 0."
This is called on-off keying. I'm not sure if Goetzel is the optimal method for demodulating this in digital, but at least one person recommends it.
Best Answer
Your best bet is going to be from the applications notes of manufacturers who sell chipsets into this market. Like Maxim semi, ST, Analog devices, Avago, NXP etc.