While geohot may have beaten the DevTeam to a 3GS jailbreak, they were not far behind - redsn0w 0.8 (the DevTeam's official jailbreak tool for all 3.0+ iDevices) has just been released, and is compatible with the iPhone 3GS.
Oh, and check it out - works on Linux too!
EDIT: To clarify, this is NOT compatible with 3.1 - 3.0 only.
redsn0w is a easy to use, multi-platform, multi-device jailbreaking and unlocking tool for the iPhone 2G (original iPhone), the iPhone 3G/3GS and also the iPod touch(1st generation and second generation). Currently it is available for Windows, Mac OS X and Linux.
OS X Guide HERE
The downloads are available via: