To open the ports for multiplayer, you need to go to Control Panel->Windows Firewall.
FOR VISTA:
There will then be a link to "allow a program through the firewall". If you click the link, then you can either add a program, or add a port.
FOR XP:
Go to the "exceptions" tab.
In either case, you'll want to add ports, so click the "Add Port" button. Add UDP port 6000 and then UDP port 6112. When you open a port it'll ask you to name them, but it doesn't matter what you name them. I went with PM2008 Multiplayer 1 and PM2008 Multiplayer 2 for my port names.
Try opening the ports in your firewall first and see if that fixes the problem. Forwarding from the router is an additional step that you can do, but it's not necessary for everyone. So don't worry about it unless you have to.