iPhone Development Team has released the software unlock for the iPhone 3G via Cydia and Installer. The same currently works with iPhone running firmware version 2.2 (yes the latest). Incidentally the iPhone Dev-Team had earlier warned against updating to V2.2, but somehow they managed to release the yellowsn0w tool for baseband version 02.28.00, the one that installs with firmware 2.2.
So, Step 1:
Jailbreak your iPhone 3G
Step 2:
Add the repositories given here in Cydia or Installer and apply the package
Also, read the complete instructions given along with the repositories in the official blog post by iPhone Development Team.