These are instructions on how to jailbreak your iPhone 3GS on the 3.1.2 iPhone firmware using RedSn0w for Windows. The Mac version of this tutorial is here. The 3G version of this tutorial ishere . The 2G version of this tutorial is here
This tutorial can be used to jailbreak before applying the BlackSn0w unlock. You can find instructions on how to apply the unlock here.
Create a folder on your desktop called Pwnage
Download RedSn0w from here and place it in the Pwnage folder. Likewise, download the latest 3.1.2 firmware from below and place it in the same folder.