Here's what you need to do:
Go into Settings, then in the 3rd group, General, then About. Write down the IMEA number. You'll need that next.
If you're giving a phone to someone else, the giver of the phone must do the unlocking. You need the wireless phone number (the phone number the phone used to be if you've upgraded), the IMEA number (above), name, email address, last 4 digits of your SSN, and your account passcode (if you have one). You can either call customer service with this information, or use this web form:
You request unlock and a few days later, assuming all goes well, the phone will be unlocked.
In order to complete the unlocking process you will need:
A computer with iTunes installed (preferably an up-to-date copy of it)
USB cable (30-pin Apple iPhone/iPad/iPod cable up to and including the 4S, Lightning for the iPhone 5)
A working SIM card
The last one bears noting: If you've upgraded you probably have the old SIM card in the old phone, and it does not work; you can't place a call with it. This will not work for unlocking! In theory you could use the SIM card from your new phone to unlock, but that gets tricky if your phones have different SIM card sizes (3GS and earlier: mini also known as "normal," 4 and later: micro).
Your best bet is to acquire whatever SIM card you intend to get and use that. If you intend to take your phone overseas you probably ought to get a cheap US prepaid SIM card and unlock before you leave. You can get a T-Mobile pre-paid SIM card for $ 1 from their web site. Make sure you get the correct size!
Turn off the phone, remove the old SIM card and install the new one. You'll need a pointy object, a small paperclip works well, to pop out the SIM card tray. It's either on the top or side of the iPhone, depending on which model it is.
Turn the phone on, wait for it to finish starting up, then connect it with the USB cable to your computer and run iTunes if it doesn't start automatically.
If you are really lucky, iTunes will just pop up a window that says your phone has been carrier unlocked. Otherwise, back up your phone. Then restore it to factory defaults. The act of doing this will reset the carrier settings and unlock your phone.
If you're giving the phone away, now it's wiped clean and perfect for gifting. If you're keeping your phone, you can then restore your old apps and data from the backup and the phone will remain unlocked.
I'm not really sure if the recipient of gifted phone can do the iTunes steps. I'm pretty sure carrier unlock occurs when iTunes recognizes your IMEA because your AT&T account and iTunes account aren't linked. So, maybe it works, maybe it doesn't. Normally the original owner would do the iTunes step so they can wipe all of their personal data off the phone, anyway.
Here's my T-Mobile iPhone 3:
Important Caveat for T-Mobile (and Straight Talk, which I think uses the T-Mobile network): It is possible that data may not work. You can use the phone as a phone, do SMS text messages and Wi-Fi connections, but there might be a problem with 3G data. I read some posts that said EDGE (2.5G) and 4G work, but 3G doesn't. Also, you need to change your APN setting. In any case, I never tried it because since I'm using a cheap pre-paid calling plan, I don't have data enabled, anyway.