Finally- a Jailbreak for the iPhone 3GS: BlackRa1n Tutorial
This does not allow for unlocking the carrier on the phone- this allows the iPhone to install applications from other sources (such as Cydia, Rock or Icy).
Very easy to do:
This version is Windows only. Your iPhone should be updated to 3.1.2 and connected to the latest iTunes.
Download the BlackRa1n.com app (click on the Windows logo). Run the app and click the ‘Make it Rain’ button.
Blackra1n does its work and reboots. After the reboot there is a new ‘blackra1n’ app on your phone. Click it to install Cydia/Rock/Ice.