Dev Team statement,

Last night we released updated versions of our redsn0w jailbreak and ultrasn0w carrier unlock. These versions are now compatible with the iPhone 3GS running at 3.0. Welcome aboard, 3GS owners! (The tools of course remain compatible with all of the other platforms too.) Also last night, saurik released 3GS-compatible versions of MobileSubstrate and WinterBoard, components that enable many different add-ons and themes.
We realize we upset some folks (e.g. existing 3GS owners) with our earlier announcement that we wanted to hold onto the 3GS iBoot-family hole until 3.1 was out. Our aim there was to get as many people as possible onboard (within reason of course) before revealing the hole, since Apple will fix it immediately. But all of that became moot when the purplera1n release was made, since it uses the same hole.
For those of you who already own 3GS phones, the outlook is bright. As long as you have your personalized (signed) dfu/img3 files, you’ll always be able to jailbreak (even if you slip up and install stock Apple firmware in the future). For those of you without 3GS phones, it’s a race against the clock to use this particular hole. There’s nothing we can do about that, but we will always be looking for new holes.
ultrasn0w unlockers — You all must remain particularly vigilant against upgrading your basebands, since doing so will kill the unlock (for most phones, there’s no going backwards in baseband version). Apple has gotten very serious with the latest baseband — they’ve removed 180 (!) commands in an effort to cut down their exposure to holes. So please always stay away from stock Apple IPSWs and instead use our tools as we release them. These tools let you update your firmware without updating your baseband.

Those installing ultrasn0w will probably also need to do a single run of Settings->General->Reset->Reset Network Settings. We’re testing various fixes for that particular glitch.
Once again, thanks to @Oranav for finding the new injection vector that allowed us to transform yellowsn0w for baseband 02.28 into ultrasn0w for baseband 04.26, and for not revealing it to Apple before it could be used where it would be most effective — firmware 3.0.
redsn0w platforms — This is the first redsn0w release that also supports linux! It’s the newest version of the bunch, so any feedback would be appreciated. But right now, redsn0w should work on OS X, Windows, and linux.

How to get the goods:

• The redsn0w torrent seeds are all here. Any direct mirroring help would also be appreciated.
• The updates to ultrasn0w, MobileSubstrate, and WinterBoard are all handled directly through Cydia (after you’ve jailbroken!)
• The Cydia repo for ultrasn0w is http://repo666.ultrasn0w.com (that last o in ultrasn0w is the number 0!)