How does Skype work without port forwarding?

Skype works in a very interesting way. From what I've read (and this is a while ago) it works as follows:

• Skype server maintains a list of all users and IPs.
• Skype user A wants to speak to user B
• Skype user A sends a network packet to user B's IP address and waits for a response. (user B never gets this packet).
• Skype user A notifies server of IP/port combination on which it is waiting for a response
• Server notifies user B to send a response to user A on the specified port
• A connection is made.

This is probably over simplified but last I checked, this is how it works. (Someone correct me if I'm wrong).

Edit: fixed bullet issue

UDP hole punching is (one) of ways how to traverse through the NAT.

You have to use an intermediary server, and initiate communication from the client side. As Yossarian mentioned, from that point one possibility is UDP hole punching. Depending on the type of application (and whether it's truly P2P or not) you might keep the go-between server in place the entire time.