I've unlocked iPhones by calling AT&T and doing an internet chat. By far, the chat was the easier of the two. However, you can now simply submit a form. I would try the form first, and do it ASAP. It can take a couple days to process the unlock with AT&T and Apple's systems.

When unlocking an iPhone, you don't get an unlock code like with a normal phone. The lock status gets changed in Apple's systems and requires you to restore the iPhone through iTunes to unlock. Backup your phone before you do this since the restore will revert the phone to a factory-fresh image.