Unfortunately I can't post links here yet but if you google "jailbreak 3GS 3.1.2 redsn0w" you should get links from redmondpie.com which I have found quite good and they will take you all the way through the process. Make sure you read the instructions VERY CAREFULLY, and several times since you probably only get one shot at this and if something goes wrong you could be stuck having to restore to 3.1.3 and no jailbreak.
Originally Posted by Calinan
You may already know this but a tethered jailbreak means you'll have to jailbreak every time you need to reboot or shutdown the phone (not standby, a complete restart).
Also, make sure you know if you have the old or new bootrom, this is very important when running redsn0w and it will ask you. Again, if you google something like "how to find 3gs bootrom version" you should get links that will explain how to do it. Based on your serial number I'm pretty sure you've got the new one but you may want to double check.