Protocol: we used a custom psuedo-TCP protocol built on UDP based on libjingle from Google (used in Google Talk): http://code.google.com/apis/talk/libjingle/file_share.html. Libjingle's filesharing itself was a decent resource for learning some P2P stuff as well.
NATing and routing: we used Skype's UDP hole punching: http://www.h-online.com/security/features/How-Skype-Co-get-r....
Skype configures each install to be a supernode by default and then disables it based on certain criteria (low speeds, behind a NAT/firewall, etc.). Discovery of other network nodes is an entire subject unto itself and a lot of other network discovery protocols are well documented; our system used a central server to track up-time statistically and map clients to one another based on finding a good fit. Happy to answer any questions here or at my e-mail address in profile.
"An Experimental Study of the Skype Peer-to-Peer VoIP System" http://saikat.guha.cc/pub/iptps06-skype/