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 (mac jailbreak guide | win jailbreak guide) or jailbroken iPhone 3G (mac/win jailbreak guide) to 4.0 you can unlock it!

Turn on wifi and connect to your network.

Go to Cydia.