These are much easier instructions on how to unlock your iPhone using SAM. This method will work with the iPhone 4S, iPhone 4, iPhone 3GS, and iPhone 3G on any jailbreakable firmware including 5.x. The original instructions can be found here.
Jailbreak your iPhone. You can find instructions on how to do that using the PandaApp Jailbreak Channel.
Tap to launch Cydia from your SpringBoard.
Press to select Manage from the tabs at the bottom of the screen.
Press the large Sources button.
Press the Edit button at the top right of the screen.
Press the Add button that appears at the top left of the screen.
Enter http://repo.bingner.com and press the Add Source button.
Press the large Return to Cydia button.
Press to select Bingner from the list of Sources.
Choose SAM from the list of packages.
Press the Install button at the top right of the screen.
Press the Confirm button to begin installation.
Once installation has completed press the large Reload SpringBoard button.
Insert your new SIM card and tap to select SAMPrefs from your SpringBoard.
Make sure your Method is set to Auto Detect and tap Utilities. Note**: If Auto-Detect doesn't work you can change Method to By Country and Carrier and select the phone's ORIGINAL carrier manually.
Press the Attempt Activation button. If you don't see Attempt Activation then select De-Activate iPhone and the Attempt Activation button should appear.
A popup will appear letting you know that "this may take a while".
Eventually your iPhone will respring and after searching for a bit your new network will be detected!
You should now backup your iPhone unlock ticket in case this method is ever blocked. You can find instructions on how to backup the unlock ticket here.
Your phone will work normally with your SIM card and that SIM card ONLY since we have tricked iTunes to think that ICCID is one of the intended carrier's. The phone can be rebooted and connected to iTunes freely without losing the "unlock", at least for now.
A big thanks to Sam Bingner, Loktar_Sun and Laforet for their contributions!