All current iPhone 3GS/3G basebands can be unlocked on firmware 4.0 using the dev team's ultrasn0w 0.93. That means if your jailbroken your iPhone 3GS old bootrom or jailbroken iPhone 3G to 4.0 you can unlock it!
Turn on wifi and connect to your network.
Go to Cydia.
Go to Manage. Tap Sources.
Tap Add. Type in repo666.ultrasn0w.com. Tap Add Source.
Tap Install. Then tap Confirm.
Cydia installs ultrasn0w.
Tap Reboot Device
Your device reboots and now you should be unlocked!