You create a custom ipsw and stitch the shsh blobs you have available on cydias server for that particular version for that iphone 3GS.
Then restore to the custom ipsw/firmware of your choice by first using redsnow to put your iphone in pwned dfu mode.
Then open itunes and select the custom ipsw.
Then once its done restoring and phone turns on you again use redsnow to downgrade your baseband from 06.15.00 to 05.13.04
Then you open cydia and install ultrasnow to unlock it.
That's it.
You're welcome, have a good nite