Currently peer discovery is implemented with a centralized server. The server waits for N users to connect, then sends a message containing the IP Address and port of all participants. This approach is vulnerable to denial of service and is a single point of failure, but on the up-side any compliant server can be used. I still believe distributed peer discovery is ideal, but that can always be added later.
The centralized method is also NAT-friendly if Tor is used. Here is an idea for anonymous peer discovery and communication:
1. Each participant starts a Tor Hidden Service.
2. Using Tor, each participant connects to a peer discovery server, which is itself a Hidden Service. It announces the ID of its Hidden Service and open port.
3. The server then sends each participant a list of the Hidden Services. The participants then connect to these Servers and proceed with the decentralized CoinJoin process.
+ No traffic ever leaves the Tor network
+ No port forwarding / NAT traversal is required (in this sense it is more user-friendly than a non-anonymous
It should be noted that in order to prevent inputs and outputs from being linked by participants more complicated measures such as the blind signatures discussed on the first page must be used.
P.S.
Here is an example of a 10-way CoinJoin I generated using my library:
http://tbtc.blockr.io/tx/info/894d10fea8e017789e80e2965d3421572e42e19ba8c6f51ce4a22b3c40b0f831This is similar to what a CoinJoin transaction would look like in practice, except a more secure implementation would mix the outputs around better.