UPDATE: Apple latest firmware is iOS 5.1.1. Apple has stopped signing all other firmwares, including iOS 5.0.1, iOS 4.3.3 and iOS 4.3.5. This means you can NOT restore to 5.0.1/4.3.3/4.3.5 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 only for iOS 4.3.3 via JailbreakMe and and iOS 5.0.1 via Absenthe.
iPhone 4S jailbreak is available for iOS 5.0 / iOS 5.0.1 via Absenthe.
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).
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.
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.
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 / iOS 5.1.1
For now only tethered jailbreak is available for iPhone 4/3GS, iPad 1 and iPod Touch 3G/4G for iOS 5.1 and iOS 5.1.1.
Famous iPhone hacker Stefan Esser, also known as i0n1c, recently wrote on twitter that we should not expect untether jailbreak for iOS 4.3.4 anytime soon. i0n1c was the one who created untether for iOS 4.3.3firmware.
Our advice is simple – save your 4.3.3 SHSH keys asap. With these SHSH keys you will be able to restore to iOS 4.3.3 anytime, without – only iOS 4.3.4. Here are tutorials for you.
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)