It's supposed to "just work". In an iPhone review (at Ars? One of the big sites.) they tested this, and it worked fine for home use (home users usually do have a firewall...), it only choked, sometimes, on corporate firewalls.
http://support.apple.com/kb/HT4245
"To use FaceTime on a restricted Wi-Fi network, port forwarding must be enabled for ports 53, 80, 443, 4080, 5223, and 16393-16472 (UDP)"
Regardless, my point was that it would almost certainly not work on a military base. They have gone so far as to ban all camera phones in Iraq, real time video conferencing outside of the military's view is not going to be allowed in combat areas. It also wouldn't look to great over satellite.
FaceTime uses uPnP, which is supported on just about any router you'd buy for under $200 at your local retailer. If you're able to play XBox or PS3 online, your iPhone should connect a FaceTime call without trouble.