From http://www.iphonehacks.com/2010/08/jailbreakme-20-released-t...
"Update 4:
If you want to unlock your iPhone 3GS and iPhone 3G then you need to first jailbreak your iPhone on iOS 4 or iOS 4.0.1 using JailbreakMe and then install Ultrasn0w 0.93 to unlock your iPhone."