ultrasn0w 0.93 released! Cydia repo is repo666.ultrasn0w.com. Works with basebands 04.26.08 thru 05.13.04 (that includes 3.1.3 and also 4.0 once it is jailbroken)
Will work in conjunction with Spirit jailbreak to allow unlock on OS 3.1.3 or 3.1.2
Ultrasn0w unlock can only be installed on jailbroken iPhones
Beta jailbreak of 4.0 iOS via redsn0w is available for iPhone 3G and iPod touch 2G.
There is no iPhone devteam official 3GS jailbreak for the released version of 4.0 iOS yet. Pwnagetool 4.0 will be released soon and will support 3GS with old bootrom that have stayed on the pwnagetrain since OS 3.1.2 and earlier. See http://blog.iphone-dev.org/post/722633863/all-four-one for details on the latest jailbreak status.