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....
CAN sounds the most applicable in this case. The distances inside a house can be handled by CAN at 500 kbits/s, which sounds like plenty of bandwidth for your needs. The last node can be a off the shelf USB to CAN interface. That allows software in the computer to send CAN messages and see all the messages on the bus. The rest is software if you want to present this to the outside world as a TCP server or something.
CAN is the only communications means you mentioned that is actually a bus, except for rolling your own with I/O lines. All the others are point to point, including ethernet. Ethernet can be made to logically look like a bus with switches, but individual connections are still point to point and getting the logical bus topology will be expensive. The firmware overhead on each processor is also considerably more than CAN.
The nice part about CAN is that the lowest few protocol layers are handled in the hardware. For example, multiple nodes can try to transmit at the same time, but the hardware takes care of detecting and dealing with collisions. The hardware takes care of sending and receiving whole packets, including CRC checksum generation and validation.
Your reasons for avoiding PICs don't make any sense. There are many designs for programmers out there for building your own. One is my LProg, with the schematic available from the bottom of that page. However, building your own won't be cost effective unless you value your time at pennies/hour. It's also about more than just the programmer. You'll need something that aids with debugging. The Microchip PicKit 2 or 3 are very low cost programmers and debuggers. Although I have no personal experience with them, I hear of others using them routinely.
Added:
I see some recommendations for RS-485, but that is not a good idea compared to CAN. RS-485 is a electrical-only standard. It is a differential bus, so does allow for multiple nodes and has good noise immunity. However, CAN has all that too, plus a lot more. CAN is also usually implemented as a differential bus. Some argue that RS-485 is simple to interface to electrically. This is true, but so is CAN. Either way a single chip does it. In the case of CAN, the MCP2551 is a good example.
So CAN and RS-485 have pretty much the same advantages electrically. The big advantage of CAN is above that layer. With RS-485 there is nothing above that layer. You are on your own. It is possible to design a protocol that deals with bus arbitration, packet verification, timeouts, retries, etc, but to actually get this right is a lot more tricky than most people realize.
The CAN protocol defines packets, checksums, collision handling, retries, etc. Not only is it already there and thought out and tested, but the really big advantage is that it is implemented directly in silicon on many microcontrollers. The firmware interfaces to the CAN peripheral at the level of sending and receiving packets. For sending, the hardware does the colllision detection, backoff, retry, and CRC checksum generation. For receiving, it does the packet detection, clock skew adjusting, and CRC checksum validation. Yes the CAN peripheral will take more firmware to drive than a UART such as is often used with RS-485, but it takes a lot less code overall since the silicon handles so much of the low level protocol details.
In short, RS-485 is from a bygone era and makes little sense for new systems today. The main issue seems to be people who used RS-485 in the past clinging to it and thinking CAN is "complicated" somehow. The low levels of CAN are complicated, but so is any competent RS-485 implementation. Note that several well known protocols based on RS-485 have been replaced by newer versions based on CAN. NMEA2000 is one example of such a newer CAN-based standard. There is another automotive standard J-J1708 (based on RS-485) that is pretty much obsolete now with the CAN-based OBD-II and J-1939.
Best Answer
The best way is to use an off the shelf part. So you don't have to worry about burning your house down. That is why I mention X10. There is already a library to interface to X10
As how to do it discretely, look at the Mamba Shield it is a hacker alternative to the X10. You can see from their schematic, there is a lot to it. Note there are no relays. And they have taken HiPot in to consideration of there components and design. Note the Mamba does not have UL or equivalent. So while it is likely safe, it has not been proven to be. And it is just as expensive as the wifi shield.
The X10 is not cheap either. But it is proven. Not sure whats UL equivalent is.
More research show the X10 Pro products (different than X10) are actually UL tested. Where the PSC04 is equivalent to PL513 and PSC05 is equivalent to the TW523. both of which appear cheaper then X10's original product.
Where as it is hard to get any solution much cheaper. If you do it your self discretely low volume pricing of part costs is expensive. And off the shelf items have overhead.
The cheapest way is to use a $4@ RF Link Transmitter and RF Link Receiver pair.