Download the latest version of RedSn0w here
https://sites.google.com/a/iphone-dev.com/files/home/redsn0w_win_0.9.15b3.zip?attredirects=0&d=1
Download iOS 5.1.1 IPSW for the iPhone that matches your iPhone type
iOS 5.1.1r1 GSM:
http://appldnld.apple.com/iOS5.1.1/041-6051.2012.0525.Cvby7/iPhone3,1_5.1.1_9B208_Restore.ipsw
iOS 5.1.1 GSM:
http://appldnld.apple.com/iOS5.1.1/041-4293.20120427.3DRyb/iPhone3,1_5.1.1_9B206_Restore.ipsw
iOS 5.1.1 CDMA:
http://appldnld.apple.com/iOS5.1.1/041-4291.20120427.Zs8F0/iPhone3,3_5.1.1_9B206_Restore.ipsw
Run RedSn0w as administrator. Go to Extras > Custom IPSW, select your IPSW that you downloaded, and create a custom IPSW. This will preserve your baseband if you want to use a Geveey SIM. If you're planning on using a factory unlock/IMEI unlock, you won't need to do this. Go to Extras > Even More > Restore. Select IPSW and point it to the IPSW that you download that matches your iPhone version (either GSM or CDMA), or if you're preserving it, point it to the custom IPSW that you created. Then for blobs, click Remote. It'll automatically retrieve the blobs that matches the IPSW you're trying to restore to. Click Next. Follow the on-screen instructions. After the upgrade, if you're in recovery mode, kick it out using a Recovery Fix in the Extras > Recovery Fix in RedSn0w.
Now that you're on iOS 5.1.1, go to RedSn0w > Extras > Select IPSW. Point it to the CLEAN IPSW that you downloaded, not the one you created. Click back, click Jailbreak. Tick "Install Cydia". Follow the on-screen instructions.