All you need is to download the iOS 6 IPSW from the sticky here for your 3GS
http://www.iphoneforums.net/forum/i...ple-ios-firmware-download-links-iphone-22984/
Then put your device into DFU mode by following the instructions here
http://www.iphoneforums.net/forum/iphone-jailbreaking-17/dfu-mode-dummies-16020/
Then follow the first link and the text below to get rid of any 3194 errors.
Fix iTunes Error 3194 When Restoring / Updating To Stock or Custom 4.3.3 Firmware | Redmond Pie
Go to C:\Windows\System 32\drivers\etc\
Delete host.umbrella
Edit your host file by right clicking, then open or open with. Then use notepad. Delete ANY lines with gs.apple.com in them. Then save.
In iTunes, shift + click restore on iTunes, then point it to the IPSW downloaded. Wait for your device to be restored to iOS 6.
Download RedSn0w, run it as administrator, then go to Extras > Select IPSW. Again, select the IPSW you downloaded for iOS 6 for your 3GS. Then go back to the starting page, and press Jailbreak. Put your iPhone into DFU on your own or follow the on-screen instructions that will guide you with the counting and actions and all. Make sure you tick "Install Cydia". Then proceed. It'll show a pineapple on your iPhone with a loading bar, then a stream of white text. When it's done, put your device back into DFU mode, then go to RedSn0w > Extras > Just Boot and it'll boot your device.