It exploits common default rules in firewalls. ie. to allow web surfing, a firewall will allow port 80, but most of the time it will allow both outbound and inbound 80, rather than just outbound. Skype will listen on a bunch of common ports (80, 25, 110, 443, etc.) and blast out connection requests, and then wait to see which port it actually receives a response on. It will also fall back on using UPnP to find a way through - a protocol that is often overlooked by network admins.
If you netstat while running skype, you will see it listening on a bunch of ports. It often prevents a local web server from starting up. The way it does this is a lot more interesting than the actual NAT punching - skype and kazaa will almost always find a way in and out of a network and they are a pain to block. Joost is also using the same tech stack.