@pirateninja
I travel to Germany several times per year and have AT&T in the US. Calls while you're in Germany are $0.99 per minute. They'll let you buy an international data package too, but they're really expensive. It's like 20 MB for $20 and $5 per MB overages.
While I don't think AT&T will unlock the phone for you, I"m sure they would have to let you out of your contract (or at least freeze it) if you were deployed and are in the military (it sounds like that from your post). You would then have to jailbreak and unlock your phone to use it on Vodaphone or Tmobile.
If you choose to use Skype, you would have to have access to Wifi, but this is definitely a cheap option.