I am using a recently updated iPhone 3GS 5.0.1 and this is how I jailbroke it using redsnow on Windows 7.

Prerequisites

1. iTunes
2. Redsnow
3. Internet connection

This is fairly simple

1. Install iTunes
2. Make sure your iPhone is updated to 5.0.1
3. Run redsnow as administrator
4. Select Jailbreak
5. Follow the instructions to put your phone in DFU mode (on windows I had to do this twice because windows 7 first looks for updated drivers on the internet)
6. Select install Cydia, press next
7. wait until redsnow shows done

Thats it, your iPhone reboots with cydia installed (This will take a couple of minutes)