Good advice from Samantha and to open the specific ports you need, Port Forward should be able to help.
http://portforward.com/
You choose what game it is and your modem (or one similar if yours isn't listed) and follow the instructions. If you can't find instructions to work with your modem, you can ask in the forum for help.
NAT is not actually about constantly changing your IP address. It's about changing the IP from the one used on the internet to the one your computer uses when data is being sent here and there. I'll quote a section from Samantha because it's well put (best answer for her? :-) )
"Your ISP provides a single public routable address and your linksys creates an internal network using a private address range that allows you to connect several internal devices"
For the single public address, assigned by your ISP, visit http://whatismyip.com
For the private address of your computer, open a command prompt window (black window you have to type in) and type ipconfig and press Enter. It's probably something like 192.168.1.3 and has a line underneath that says the subnet mask is 255.255.255.0
"however once it routes past your linksys router all of the internal devices will appear to the internet as the same address."
Your router takes care of working out what IP address to use as it sends data back and forth. That's NAT. NAT stands for Network Address Translation, in other words, swapping the IP address being used for the one needed for the next trip the data is taking - your router is doing that.
Your modem needs telling what to do with traffic that comes in and that's the port forwarding part. Visit Port Forward for help on that and/or ask in the game forums.