The latest firmware update that brought us iOS 4.0.1 did not update the baseband which remains at version 05.13.04. This means that if you have an iPhone 3G, you can jailbreak iOS 4.0.1 and unlock your it with UltraSn0w.
Step 1: You will have to jailbreak your iPhone 3G iOS 4.0.1 first.
Step 2: Then simply add this source to Cydia: http://repo666.ultrasn0w.com. More details here.
Step 3: Finally, search for “UltraSn0w” in Cydia and install the application. Reboot your iPhone, and you’re done. You can now use your iPhone on a different carrier.
There is no iOS 4 jailbreak for iPhone 3GS and iPhone 4 yet but I guess it’s just a matter of time now.