Even though iOS 6 has only been out for a day, the folks over at iPhone Dev-Team have already released a Redsn0w jailbreak that works on the iPhone 4, iPhone 3GS, and iPod touch (fourth generation). As of right now, there's only a tethered jailbreak available, which means that you'll have to connect your device to your computer every time you power it up, but an untethered version that works on more devices is more than likely on the way. Until then, tethered is better than nothing, so here's how to do it.
Before you get started, make sure you have the latest version of iTunes installed. If not, you'll need to download it first.
Plug in your device and put it in DFU mode. It's also a good idea to backup your data in case anything goes wrong. Next, download the jailbreak for your OS. You can find it here for Windows and here for Mac.
After downloading, extract the file and save it to your desktop. Open the Redsn0w file and click on the Extras option, then choose Select IPSW. From here, install instructions should pop up on your screen, so just follow those and you're all set. Check out the video to see it done step by step, and for how to install Cydia.