Good, comprehensive guide to unlocking mobile phones by Schuyler Earle. Anyone know when I can get a phone-unlocker for OS X? Update: You can always use the Web-based unlocker if you don't mind sending a stranger your IMEI.
The locktype, according to unlockme.co.uk, is usually 2, unless you're on a 3650 or 7650, in which case it's 5. The IMEI is the hardware serial number of your phone, which you can read off the inside label underneath the battery, or retrieve from the phone itself by dialing *#06#. Finally, you'll need the provider code, which is a 5-digit number you can pull from this network provider code list. Unlock code calculators give you seven different codes, at least one of which should unlock the phone when entered with the SIM removed, but you only get five tries, before the phone locks you out. So, you really want to double-check your work before entering would-be unlock codes into the phone.
(Thanks, Schulyer!)