"Geohot," who was the first to jailbreak the original 2G iPhone (albeit with a bit of hardware tweaking) and also the first to jailbreak the iPhone 3GS has released the first jailbreak for the latest iPhone firmware, 3.1.2. The iPhone Dev Team still hasn't completed a jailbreak for the iPhone 3GS on the last firmware (except for previously jailbroken iPhone 3GS's).
Unfortunately for Mac users, it's Windows only for now, but I suppose that's what Boot Camp is for. At any rate, the .EXE for the jailbreak, dubbed "blackra1n," is downloadable here (click the Windows icon). Assuming you've already updated to 3.1.2, here's how it works:
Step 1: Start blackra1n. It might be necessary to run the app in "XP Compatibility Mode" on Vista or 7 but I didn't see an issue.
Step 2: Click on “make it ra1n”:
Step 3: Wait for the phone to automatically reboot.
Step 4: You should see “blackra1n” in your iPhone app list . Run “blackra1n”, download "Cydia" and install it.
Step 5: Reboot your iPhone. You should now be running a jailbroken version of firmware 3.1.2 on your iPhone or iPod touch.
Of course, your mileage may vary. No notes from the iPhone Dev Team yet about their opinion on Geohot's latest "blackra1n" version.