UPDATE: Apple released iOS 5.1 firmware. Apple has stopped signing iOS 5.0.1, so you can NOT restore to 5.0.1 any more. If you are on 5.0.1 you can jailbreak with RedSn0w.
Using this tutorial you will be able to untether jailbreak iOS 5.0.1 running on iPhone 4. Pwnagetool will also preserve baseband version if you need carrier unlock. This tutorial uses PwnageTool 5.0.1 for Mac OS X.
UPDATE: Apple released iOS 5.1 firmware. Apple has stopped signing iOS 5.0.1, so you can NOT restore to 5.0.1 any more. If you are on 5.0.1 you can jailbreak with RedSn0w.
Using this tutorial you will be able to untether jailbreak iOS 5.0.1 running on iPhone 3GS. Pwnagetool will also preserve baseband version if you need carrier unlock. If you have updated the baseband to version 06.15, you can use this tutorial to update to iOS 5.0.1. This tutorial uses PwnageTool 5.0.1 for Mac OS X.
The iPhone Dev-Team has updated PwnageTool with support for the iOS 5.0.1 untethered jailbreak. PwnageTool lets you easily create a custom ipsw for upgrading to iOS 5.0.1.
Unlockers can use custim firmware to preserve baseband version and unlock with ultrasn0w or gevey. Depending on your device you can also configure the ipsw with boot logos and Cydia packages.
PwnageTool 5.0.1 supports iPhone 3GS, iPhone 4, iPad 1, Apple TV 2G, iPod Touch 3G, iPod Touch 4G.
You can download the new version of PwnageTool 5.0.1 from here.
UPDATE: Here are our step-by-step tutorials that will guide you through all the process of untethered jailbreaking iOS 5.0.1 with PwangeTool 5.0.1:
UPDATE: Apple released new iOS versions and has stopped signing all other firmwares, including iOS 6.1.2 and iOS 5.1.1. This means you can NOT restore to 6.1.2/5.1.1/4.3.3 and others any more (both original and custom), unless you have saved your SHSH keys for it.
If you have decided to perform an untethered jailbreak and unlock, you need to get the following information:
What type of device do you have (iPhone 3G/3GS/4, iPod Touch 3G/4G, iPad 1/2, Apple TV)?
Do you need unlock (if your iPhone locked to one carrier and you want to use it with another)?
The answer is NO, if the device is not iPhone, if it was purchased as factory unlocked and can be used with any cellular carrier (f.e. in Canada, France, etc).
If the answer is YES, you need to find out your modem version (Setting-General-About-Modem).
What firmware version do you have? Take a look at Setting-General-About-Version. For example it could be iOS 4.3.3.
What operating system do you use on your desktop (Windows, Mac OS)?
How to perform jailbreak, when you do NOT need an unlock
For iPhone 3G the latest is iOS 4.2.1. You can perform jailbreak with any utility. For iOS 4.2.1 you can also use them or GreenPois0n (Windows, Mac OS).
iPad 2 jailbreak is available for iOS 4.3.3 via JailbreakMe and iOS 5.0.1 / iOS 5.1.1 via Absinthe, iOS 6.0-6.1.2 and iOS 7.0-7.0.4 via Evasi0n, iOS 7.1-8.1 via Pangu, iOS 8.1.1-8.4 via TaiG, untethered iOS 9.0-9.0.2 via Pangu9.
iPad 3 jailbreak is available for iOS iOS 5.1.1 via Absinthe, iOS 6.0-6.1.2 and iOS 7.0-7.0.4 via Evasi0n, iOS 7.1-8.1 via Pangu, iOS 8.1.1-8.4 via TaiG, untethered iOS 9.0-9.0.2 via Pangu9.
iPhone 4S jailbreak is available for iOS 5.0 / iOS 5.0.1/ iOS 5.1.1 via Absinthe, iOS 6.0-6.1.2 and iOS 7.0-7.0.4 via Evasi0n, iOS 7.1-8.1 via Pangu, iOS 8.1.1-8.4 via TaiG, untethered iOS 9.0-9.0.2 via Pangu9.
iPhone 3GS, iPhone 4, iPod Touch 3G, iPod Touch 4G, iPad jailbreak is untethered for iOS 5.1.1 and iOS 6.0-6.1.4.
iPhone 5/5C/5S/6/6plus, iPad 4, iPod Touch 5G jailbreak is untethered for iOS 6.0-6.1.2 and iOS 7.0-7.0.4 via Evasi0n, untethered for iOS 7.1-8.1 via Pangu, iOS 8.1.1-8.4 via TaiG, untethered iOS 9.0-9.0.2 via Pangu9.
iPhone 6S / 6S+ / 6 / 6+ jailbreak is untethered for iOS 8.1.1-8.4 via TaiG, untethered iOS 9.0-9.0.2 via Pangu9.
iPad Mini / Mini 2 / Mini 3 / Mini 4 / Air / Air 2 jailbreak is untethered for iOS 7.0-7.0.4 via Evasi0n, untethered for iOS 7.1-8.1 via Pangu, iOS 8.1.1-8.4 via TaiG, untethered iOS 9.0-9.0.2 via Pangu9.
iOS 4.3.3
Apple stopped signing iOS 4.3.3, so you cannot update to iOS 4.3.3 without SHSH keys saved (in advance some time ago). If you have iPhone 4, iPhone 3GS, iPad 1, iPod Touch 3G or iPod Touch 4G that run iOS 4.3.3 - use JailbreakMe or RedSn0w to untether jailbreak your device.
If you have saved SHSH keys for iOS 4.3.3 you can use PwnageTool (Mac OS) or Sn0wBreeze (Windows).
iOS 4.3.4/4.3.5
For iOS 4.3.4/4.3.5 only tethered jailbreak is possible with redsn0w. Tethered means that each time you restart your device you will have to connect it to a computer and run redsn0w. The untethered iOS 4.3.5 jailbreak is possible only for iPhone 3GS with old bootrom. You can detect your bootrom version using this tutorial.
iOS 5
To jailbreak and unlock iOS 5 use latest version of redsn0w 0.9.9 or sn0wbreeze 2.8. You can jailbreak tethered or semi-tethered.
The untethered iOS 5 jailbreak is possible only for iPhone 3GS with old bootrom. You can detect your bootrom version using this tutorial.
iOS 5.0.1
For iPhone 4/3GS, iPad 1, iPod Touch 3G/4G an untethered jailbreak is available for iOS 5.0.1. For untethered jailbreak use the latest redsn0w 0.9.10 or Corona - package from Cydia to untether currently installed tethered jailbreak.
Tutorial how to untether installed tethered jailbreak is available here.
For iPhone 4S and iPad 2 use Absenthe.
For tethered iOS 5.0.1 jailbreak you an use redsn0w 0.9.9 and sn0wbreeze 2.8.
iOS 5.1
For now only tethered jailbreak is available for iPhone 4/3GS, iPad 1 and iPod Touch 3G/4G for iOS 5.1.
iOS 5.1.1
You can do an untethered jailbreak for iPhone 4S, iPhone 4, iPhone 3GS, iPad 3, iPad 2, iPad 1, iPod Touch 3G, iPod Touch 4G and Apple TV2G.
Use Absinthe 2.0.4 or RedSn0w 0.9.12 (for all iPhones, iPods and iPads), Sn0wBreeze 2.9.5 (for all A4 devices) and Seas0npass (for Apple TV 2G).
Tutorial how to untether installed tethered jailbreak is available here.
iOS 6.0-6.1.2
Untethered jailbreak is available for all devices with iOS 6.0 - iOS 6.1.2. It is called Evasi0n.
iOS 6.1.3-6.1.5
Tethered jailbreak is available for old devices (iPhone 3GS, iPhone 4, iPod Touch 4) and Cydia package to make it intethered.
iOS 7.0 - 7.0.4
Untethered jailbreak is available for all devices with iOS 7.x, including iPhone 5S/5C and iPad Air. Utility is called Evasi0n 7.
iOS 7.1 - 7.1.2
Untethered jailbreak is available for all devices with iOS 7.x, including iPhone 5S/5C and iPad Air. Utility is called Pangu.
iOS 8.0 - 8.1
Untethered jailbreak is available for all devices with iOS 8.x, including iPhone 5S / 5C / 6 / 6+ and iPad Air /Air 2 / Mini / Mini 2 / Mini 3. Utility is called Pangu8.
iOS 8.1.1 - 8.4
Untethered jailbreak is available for all devices with iOS 8.0-8.1.2 including iPhone 5S / 5C / 6 / 6+ and iPad Air /Air 2 / Mini / Mini 2 / Mini 3. Utility is called TaiG.
iOS 9.0 - 9.0.2
Untethered jailbreak is available for all devices with iOS 9.0-9.0.2 including iPhone 6S / 6S+ / 6 / 6+ / 5S / 5C / 6 / 6+ and iPad Air /Air 2 / Mini / Mini 2 / Mini 3. Utility is called Pangu9.
Sn0wBreeze 2.9.6(pwnagetool for windows, supports untethered jailbreak of iOS 5.1.1 for iPhone 4, iPhone 3GS, iPod Touch 3G, iPod Touch 4G, iPad and Apple TV 2G)
Sn0wBreeze 2.9.3(pwnagetool for windows, supports tethered jailbreak of iOS 5.1 for iPhone 4, iPhone 3GS, iPod Touch 3G, iPod Touch 4G, iPad; untethered for iPhone 3GS with old bootrom; untethered for iOS 5.0.1, iOS 4, iOS 3 supports Apple TV 2G)
Sn0wBreeze 2.8b11(pwnagetool for windows, supports iOS 5, iOS 5.0.1, tethered jailbreak for iPhone 4, iPhone 3GS, iPod Touch 3G, iPod Touch 4G, iPad, Apple TV 2G; untethered for iPhone 3GS with old bootrom)
Current version is ultrasn0w 1.2.3, download in Cydia (unlock for iPhone 4, iPhone 3GS, iPhone 3G, firmwares 3.0-4.3.3; it supports basebands 01.59.00, 04.26.08, 05.11.07, 05.12.01, 05.13.04, 06.15.00)