It seems that occasionally my friends and I have issues connecting with each other. I'm assuming this is a firewall/router issue, although it could be something else. Under Network Settings in the game, I have it set to 'Friends Only' so it shouldn't be an issue with my game settings.
Borderlands 2 uses steamworks, and according to Chrisf they don't use any other special ports, so the standard steam answers apply.
Dedicated or Listen Servers
Steamworks P2P Networking and Steam Voice Chat
Also, there are several ISPs which block ports required for the proper operation of Steam and Steam games:
Furthermore, Steam has their own connectivity support doc with the basic check your firewall, av software, etc. that you could try here.
The only interesting thing I see on it is starting steam with -tcp to force it to use all TCP ports instead of UDP, if that's messing something up on your end.
EDIT: I forgot that Borderlands 2 is integrated with Steam unlike the first Borderlands, so @Kexlox answer has the correct information for fixing your problem.
An alternative is for you and your friends to download a program that emulates LAN. There are many programs that do this, including GameRanger and Hamachi. I personally recommend Tunngle, as it is what me and my friends currently use and it has support for a large range of games. Not that it's the best - but Tunngle will for sure get you and your friends playing. Don't forget to change from 'Friends Only' to 'LAN' in Network Settings in-game once you have set one of these programs up!