These instructions will show you how to jailbreak 'untethered' your iPhone 3GS running iOS 5.0.1 using the Windows version of redsn0w. This is an untethered jailbreak thanks to @pod2g’s “corona” untether for iOS 5.x on A4 and earlier devices. It requires that you upgrade to iOS 5.0.1 using iTunes which may make it impossible to unlock until a solution is found by the Dev Team. If you need your unlock, you will want to create a custom ipsw file with PwnageTool that does not upgrade your baseband.

Step 1
Download and launch redsn0w (Windows, Mac).

Step 2
Select the Jailbreak button.

Step 3
Make sure your device is off and select Next.

Step 4
Follow the instructions to put your device in DFU mode.

The jailbreak process will begin. Let it run.

Step 5
By default, Install Cydia is selected. If you like, you can select other options. Click Next.

The jailbreak process will continue and then will finish on the device.

When the device reboots, you will find Cydia on your springboard, normally the second page.

Check out redsn0w's extras for things like Pwned DFU or Recovery fix.