Create a folder on your desktop called Pwnage
Download RedSn0w from here and place it in the Pwnage folder. Likewise, download the latest 5.0b4 firmware from the iOS Dev Center and place it in the same folder.
5.0b4 (3GS): iPhone2,1_5.0_9A5274d_Restore.ipsw
*Important: if you previously updated your iPhone 3GS to the 6.15 baseband you must launch RedSn0w and place your device into PwnedDFU before restoring to iOS 5.
Once iTunes has finished updating your iPhone to the desired firmware open the Pwnage folder on your desktop and launch the redsn0w application from the redsn0w folder we extracted earlier.
Click the Next button to continue
RedSn0w will now guide you through the steps to get into DFU mode. You can find more help with DFU mode here
Once this is complete you will be notified that RedSn0w is done. Click the Finish button. When your iPhone finishes rebooting (5 minutes or so) it will be jailbroken with Cydia on the SpringBoard.
Since this is a tethered jailbreak you must use Redsn0w to help you boot back into your jailbroken device if its powered off for any reason. Simply connect your iPhone to the computer, launch RedSn0w, select Just boot tethered right now from the options window and click Next to have RedSn0w boot your device.
*As usual a big thanks to the iPhone Dev-Team for their hard work and contribution to the iPhone community.