Update on unlocking iPhones
The best way to unlock modern iPhones using the most recent Apple firmwares is to use RedSn0w. Here is a guide for unlocking the 2G iPhones (such as mine). If you want to unlock a 3G or 3GS, you need to jailbreak the phone first using RedSn0w, and then unlock it using UltraSn0w, the unlocking tool for iPhone 3G.
The general website for unlocking iPhones, from the iPhone Dev-Team, can be found at their blog.