iH8sn0w, the guy behind sn0wbreeze jailbreak has just released sn0wbreeze 2.8 b2 which brings untethered jailbreak for iOS 5 beta 1 for iPhone 3GS old bootrom only, so you don't need to connect your iPhone to PC after rebooting your iPhone. Last week iH8sn0w released sn0wbreeze beta 1 which jailbreaks iPhone 4, 3GS, iTouch 4G, 3G and iPad but it was only tethered which means that you should connect to your computer on every reboot.
Mac users can jailbreak iOS 5 beta 1 tethered with Redsn0w 0.9.8 b1 - Click Here.
Download sn0wbreeze 2.8 b2 for Windows (Untethered jailbreak for iPhone 3GS old bootrom only)
Download iOS 5.0 beta 1 for developers - For Non-developers Click Here.
Download iTunes 10.5 for developers - For non-developers (Google it)
Update 1: iOS 5 Final version has been released for Download and Jailbreak - Click Here
Update 2: Jailbreak 5.0.1 untethered has been released, get it now - Click Here