If you can get an unlock code from t-mobile for your phone (or buy one off of ebay), it shouldn't be hard to get it on AT&T's network unless it's REALLY old. I know nothing about getting the unlock codes from the carriers themselves(though I've heard of some success stories), the ebay ones are actually perfectly legal, and if you look hard enough on the web, you can find some free unlock codes(though I don't know if they're phone-specific).

Just swap SIMs to the AT&T one, and it usually just works, at least for voice/sms. Special features could be an issue, but just calling/sms is pretty standardized.