UPDATED: How to jailbreak new iPhone 3GS (step by step)

- first, download and install iTunes on your pc or mac:
http://www.apple.com/itunes/download/

- Download iPhone 3GS firmware 3.0.1 from here:
http://appldnld.apple.com.edgesuite.net/content.info.apple.com/iPhone/061-6976.20090731.Vgbt5/iPhone2,1_3.0.1_7A400_Restore.ipsw

- connect your iphone to iTunes.

- update to iphone 3.0.1 in iTunes: Start iTunes then connect your phone via USB. Then WHILE HOLDING DOWN THE "SHIFT" KEY, press the "update" button in iTunes. Select the file you downloaded above: "iPhone2,1_3.0.1_7A400_Restore.ipsw"

- Download:

- Redsnow:
http://thebigboss.org/hostedfiles/redsn0w-win_0.8.zip

- iPhone firmware 3.0:
http://appldnld.apple.com.edgesuite.net/content.info.apple.com/iPhone/061-6582.20090617.LlI87/iPhone2,1_3.0_7A341_Restore.ipsw

- Run redsn0w
- Click browse
- Select the 3.0 firmware file you downloaded "iPhone2,1_3.0_7A341_Restore.ipsw"
- Click next.
- Select Cydia (not icy)
- Follow on screen instructions.
- iPhone will reboot Jailbroken. You will see a brown Cydia icon on your second screen.