UPDATE: Apple released iOS 5.1 that is only tethered jailbreakable with redsn0w. Apple has stopped signing iOS 5.0.1, so you can NOT restore to 5.0.1 any more (both original and custom), unless you have saved your SHSH keys for 5.0.1. If you are on 5.0.1 you can jailbreak with redsn0w.
Install the Cydia package prepared by the chronic devteam. It is called Corona 5.0.1 Untether. (tutorial)
2. If you are not on 5.0.1 yet, update now! If you unlock via ultrasn0w or gevey, make sure you update to 5.0.1 via a custom IPSW! See our guides for sn0wbreeze here. Once you're at 5.0.1, use the latest redsn0w 0.9.10 to both jailbreak and untether.
iPhone Dev-Team released RedSn0w 0.9.9b9 with full iOS 5.0.1 support (no need to point to iOS 5.0 any more). New version also features support for SHSH and APTickets:
native support for 5.0.1 (no need to point redsn0w at 5.0 IPSW or use command-line args). Support automatically extends to all of redsn0w’s various functions: “Jailbreak”, “Just boot”, “Fetch blobs”, “Stitch blobs”, “Recovery Fix”
iBooks fixed in 5.0 and 5.0.1. This is a targeted fix that doesn’t remove entire sandbox mechanism. 5.x users already using redsn0w “Just Boot” can just use the new version without redoing entire jailbreak again
3GS old-bootrom owners can now create custom IPSWs without blobs
ultrasn0w compatability update (i.e. same baseband requirements) for 5.0.1 will be available on Cydia Monday
support for newer 8GB iPhone4 (which until now had problems with “Fetch blobs”). Thanks to @JKjeepnJeff for loaning us one of these newer i4 units for testing!
allows Windows users (not just OS X users) to use the “Custom” button to create IPSWs without baseband updates. (Update: please wait for 0.9.9b9b for this!)
accommodates APTickets in 5.x (until next Apple countermove). APTickets are crypto-verified before submitting to Cydia, just like the main blobs. Cydia server support for sending back the APTickets is upcoming. For now, use stitched IPSWs for 5.x. Due to APTickets, stitched 5.x IPSWs now require user to start in “Pwned DFU” mode
Support added for stitching 4.x blobs to iPad2-GSM IPSWs. Similar to @notcom’s TinyCFW but doesn’t require lots of RAM or a TSS-assisted restore. Won’t work for iPad2 5.x blobs (or iPhone4S at all) until a bootrom-level exploit is out
top line now shows whether (and where) a redsn0w update is available, or if the version being run is the latest. Uses DNS TXT record to alleviate any concerns about snooping
no 5.1 beta support at this time (major apps like Cydia are not yet compatible)
@pod2g has been doing a great job porting his 5.x untether…check his blog for updates!
Owners of newer 3GS iPhones must not flash the iPad baseband. The iPad baseband will not work on 3GS iPhones built later than 2011 week 35. You have a week 35 or later device if your serial # starts with xx135.
Update #17b: Version 0.9.9b9b enables the “Custom” button for Windows users, and make the 3GS week 35 warning a more explicit part of the process.