To pull this off you'll need iUnlock + nor + the .fls file, which is available in ZIPs all over. We've got the app here, but this package doesn't include all of the files necessary. Good list of links here, or try here, here, here, here, and here.
For the how-to, just hit up one of those guides down below. Naturally, we offer zero guarantees that any of this will work. (Read: don't whine to us if your iPhone gets bricked.) Big ups to the iphone.unlock crew, Draken, and, of course, the iPhone Dev Team. Let us know in comments if this technique works for you.
Update: We've confirmed the hack! Yes, it's fully restore-resistant, too, which is great news. We'll get you all the juicy proof in a few, but we have indeed managed to software unlock an iPhone with iUnlock. Also, HaRRo says the app should be out "very soon" to make this easier on the noobs.
Update 2: Depending on activation method, YouTube might not be working after the unlock -- ours isn't. This is, of course, expected behavior. There's a Windows script here that should hopefully fix you up (again, we don't make any guarantees), but Mac users will have to look elsewhere. Also, alongside the Mac GUI iUnlock app in the works, the iPhone Dev Team is prepping a Windows version, a simple bash script and an iPhone app -- and eventually an all-in-one app that can do everything from the Jailbreak to the unlock.
Update 3: We've posted our terminal output from using the hack after the break. Go ahead. Nerd out. Also, the graphical version isn't out quiet yet, but we've got the first image of it above. Check it out.
Update 5: Ok, the graphical unlock app still isn't yet out, but we've tested an early build, and it definitely works! Check it out here.
Read - Official unlock guide
Read - Unofficial unlock guide