In October 11, 2009, blackra1n is released which is the new program for jailbreaking. So far, dev-team hasn't released any jailbreaking tool for iPhone 3GS 3.1.x, but blackra1n is working for iPhone 3GS 3.1.x.
I jailbroke the iPhone 3GS 3.1.2 with this. Following is the screen shot of the jailbroken iPhone 3GS 3.1.2.
To jailbreak an iPhone,
1. Visit http://www.blackra1n.com/
2. Click Windows icon. It makes you download blackra1n.exe.
3. Just run!
4. After rebooting, run blackra1n in your iPhone.
5. Install whatever you want among Cydia, Icy and Rock!
Now, you can install any program from Cydia, Icy or Rock!
To make jailbreaking sure, I plugged out any iPod from my computer and turned off iTune before running blackra1n.exe.
Thank you, blackra1n! You are great!
For more information: http://www.blackra1n.com/