A tethered jailbreak for iOS 5.1 is now currently available for the original iPad and the iPhone 4, and earlier model iPhones. (If you have an iPhone 4S or iPad 2, don't attempt to update to iOS 5.1 and jailbreak, it won't work.)
As always, unlockers that rely on ultrasn0w are going to want to stay away unless you use a custom IPSW to install iOS 5.1 in order to preserve your baseband.
If you are an iPhone 3GS user with an old boot room, congratulations. You can have an untethered jailbreak now on iOS 5.1. All other devices will be tethered.
I typically recommend staying away from tethered jailbreaks unless you absolutely have to. Given the fact that iOS 5.1 didn't bring too many features to the table, I'd probably stay on iOS 5.0.1 until an untethered version is released and upgrading at that time.
And I can't say this enough times: if you have an iPhone 4S or iPad 2, this does NOT apply to you.
You've been warned. If you're still convinced you need your iOS 5.1 jailbreak now, you can pick up redsn0w 0.9.10b6 via our download links below. It's available for both Mac and Windows users.