I am using a recently updated iPhone 3GS 5.0.1 and this is how I jailbroke it using redsnow on Windows 7.
Prerequisites
This is fairly simple
- Install iTunes
- Make sure your iPhone is updated to 5.0.1
- Run redsnow as administrator
- Select Jailbreak
- 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)
- Select install Cydia, press next
- wait until redsnow shows done
Thats it, your iPhone reboots with cydia installed (This will take a couple of minutes)