I know this is an old thread, but I'm posting this for future reference.
As with any multiplayer game that uses direct IP, normally if you're playing someone from behind a router you'll need to forward the ports used by the game to your computer. Unfortunately, you need to know which ports are used by the game, and I haven't been able to find what these ports are.
Thankfully, there's an easier way to play someone over the internet. I'd recommend using a program called Tunngle. Essentially it creates a virtual network between you and your friends, through which you can play LAN games. I haven't actually tested Chaos Overlords, but it should work this way
.