yellowsn0w iPhone 3G unlock has been released! This is yellowsn0w version 0.9 and it's still in beta so use it at your own risk.
Note: You must upgrade to the latest 02.28 baseband (firmware 2.2) in order to use this unlock and also jailbreak with QuickPWN/PwnageTool and add Cydia/Installer.
Here is the iPhone 3G firmware 2.2 download link:
You can install yellowsn0w 3G unlock by using either Cydia or Installer, whichever you prefer. Below is a list of the repos/sources.
Note: The DevTeam also says that once you are done installing yellowsn0w through Cydia go back to the main menu on Cydia and restart your iPhone with the 3rd party SIM installed. Wait for the slide to unlock screen, and then wait 10-15 seconds. If you don't see your carrier name pop up you must remove your SIM, insert it again, and wait 10 seconds. (The DevTeam plans on elimintating this step)
1. Install BossPrefs and Yellowsn0w from Cydia
2. Disable everything in BossPrefs
3. Reboot your iPhone using BossPrefs
4. Wait 1.30 min when you see lockscreen
5. Take your sim out and insert it
6. Wait a moment
7. In settings turn on Fly Mode
8. Turn off Fly Mode
9. Your iPhone 3G should be working now!