They don't do any NAT traversal, but that use UPnP to open ports. During a talk Gunnar Kreitz said that they still got a 60% success rate for connections (if I remember correct, varied between countries also). And that this was good enough for them. More can be read in this paper: http://www.csc.kth.se/~gkreitz/spotify-p2p11/spotify-p2p11.p...
Since I'm NATing my network and don't allow UPnP the statement that they don't do any NAT traversal seemed suspicious since I know spotify does stream to other peers from my machine (400 MB since last reboot (13 days)).
Got the answer from the paper: When a client wishes to connect to a peer, a request is also forwarded through the Spotify server asking the connectee to attempt a TCP connection back to the connecter. This means that as long as one of the two peers can accept incoming connections, the connection will succeed.
[1] Just need to predict the Internet-facing ports for both peers and then instruct them to connect() towards each other at these ports. The rest is handled natively by TCP, via the simultaneous open scenario [2].
[2] http://www.ietf.org/rfc/rfc793.txt, sect. 3.4, fig. 8