Gamespy and Manual IP
You do not need any extra software to use GameSpy, so you can select it straight from the multiplayer connection menu by right clicking on the "Internet-Tunngle" icon. After you have clicked on "GameSpy", the log-in screen should appear (again, perhaps with a second to minute long wait). All you need to do is enter a nickname (some symbols may cause errors however) and click “log in”. You do not need to register if you do not wish to. You will enter the GameSpy lobby nearly instantly after you have pressed log in. Chat is possible by using the narrow rectangular box in the bottom left of the window.
Note that although you might encounter problems with hosting or joining, these may occur simply through the routing paths, by no fault of your own.
Manual IP hosting
Of course, if you have looked at the multiplayer connection menu you will also notice a fourth option - Manual IP. For a Manual IP connection you need to know your host's IP address and the host needs to open a number of ports. For Fleet Operations, these specific ports need to be open (forwarded):
With these ports open or forwarded you should be able to host games successfully. If you are unsure of how to open/forward ports on your modem/router, PortForward.com has some excellent guides.
About Firewalls & NAT Routers
GameSpy and Direct IP internet games require some ports to be opened (See NetHelp.txt in the Fleet Operations’ data folder or click the “Help” button in the multiplayer lobby), or your computer needs to be set to DMZ. Consult your NAT router and firewall manual to see how to apply these changes.