Skip to the bottom line to avoid all the horrid details! :)
A few months back I had finally decided to try to unlock my iPhone 3G. I did lot's of searches on the easiest/best way of doing so. I came across posts about AT&T laughing or ridiculing the request. I tried a few quick solutions to the tune of $20 - $30, which turned out to be little more than links and fancy instructions to what is freely available on the Internet. So, I took the jump and jailbroke my iPhone for the first step to unlocking it, only to discover that my modem firmware was a version which could not be unlocked. There was a hack available for that as well but the risk was breaking the GPS reception, so I didn't jump. But then there was supposedly a hack to undo the modem firmware hack if it didn't work. I finally decided to try it. The unlock worked but not GPS. So, I tried the second hack to undo the modem firmware hack, well that didn't work either. I was stuck without GPS. I tried lots of ways to revert to an older iOS with working GPS to no avail. Finally, I decided to call AT&T to ask for an unlock, actually for an older, "dumber" phone. AT&T was like, sure no problem, here is the code to unlock it. So, I decided to ask about unlocking the iPhone and they asked for my info and checked on it. No problem (an older iPhone out of warranty, 2 year contract over), just sync through iTunes and now it will be unlocked. But my problem was now with a hacked iPhone, I couldn't get it to update through iTunes. So, I tried a couple of more hacks, finally got the iPhone in a state so that it would update and sync through iTunes. My iPhone is unlocked for use on any GSM carrier and I have tried it on a couple of them.
BOTTOM LINE - iPhone out of warranty and contract, just call and ask for it to be unlocked - EASY!
AT&T's FAQ even explains it.