I actually work for a company that does iPhone unlocking, so hopefully I can clear some things up.
Every iPhone (or any other phone) is originally unlocked when the manufacturer makes them. The networks then buy the phones from the manufacturer, who (upon request) then applies the lock for them.
This is legal for the networks to do because they then sell the phone at a subsidised price. The plan being that they will then generate the lost up-front revenue over the phones lifespan.
If you were to buy the phone directly from the manufacturer (the Apple store in this instance) the phones will be unlocked - unless they are being subsidised. This is how it has worked for all iPhone releases.
If however you got your iPhone on an upgrade or straight from a network, you can still unlock it using the phones IMEI. This is done through iTunes. Once the iPhone unlock request is ordered, we (or any other decent provider) then send the request to Apple who locate the phone on their servers using the IMEI. To unlock it, they tell the iTunes servers that from now on the phone should remain unlocked. The next time the phone is connected to iTunes with a non-accepted SIM card, the lock is removed and the iPhone is unlocked.
Be careful if you go down the temporary unlocking route however, because this isn't done through iTunes and the lock will become active again if you update the iOS.
More info on instructions and order details here:
http://www.mobileunlocked.co.uk/apple/iphone+5/
I hope that answers a few questions that were bouncing around, but if anyone has another one, I'll try my best to help answer it. Let me know.