ultrasn0w (the current iPhone software unlock solution) is now OFFICIALLY and completely supporting all iPhone's, including the 3GS.

It works from Linux, Windows, or OS X now as well.

You can download the 0.8 update through Cydia by adding the repo: repo666.ultrasn0w.com.