Please be aware that updating to iOS 5.1.1 will cause you to upgrade your baseband potentially ruining your chances for an unlock. Once on iOS 5.1.1 you should save your SHSH Blobs by following this tutorial.
If you want to jailbreak a lower firmware version you can find the appropriate tutorial here.
Create a folder on your desktop called Pwnage
Download the latest version of RedSn0w from here and place it in the Pwnage folder. Likewise, download the 5.1.1 firmware from here and place it in the Pwnage folder. (Note: you do not need to download the 5.1.1 firmware if you are already on iOS 5.1.1)
Extract the RedSn0w zip file by double clicking it.
Step Two: (You can skip this step if iOS 5.1.1 is already installed on your device)
Connect your iPhone to the computer and launch iTunes.
Select your iPhone from the list of devices on the left. Now hold down Option and click the Restore button. Restore is preferred as it won't create any wasted space on your iPhone.
Navigate to the Pwnage folder on your desktop and select the 5.1.1 firmware ipsw. Click the Choose button to continue.
iTunes will now update your iPhone to the new firmware.
Launch the redsn0w application from the redsn0w folder we extracted earlier.
Once RedSn0w opens click the Jailbreak button.
The Rocky Racoon jailbreak will now go through three steps to complete.
3. Finishing up:
Once this is complete you will be notified that RedSn0w is done. When your iPhone finishes rebooting (5 minutes or so) it will be jailbroken with Cydia on the SpringBoard.
*As usual a big thanks to the iPhone Dev-Team. Chronic Dev-Team, and Geohot for their hard work and contribution to the iPhone community.