If someone could back me up or refute this, go ahead. For me, I just buy the factory-unlocked phone straight from apple.com and don't have to deal with it. (I go out of the country enough that it's worth it to me).
Part of that activation process involves getting a token back that instructs the phone how it should be locked, or not at all.
The unlock process that AT&T (and every other iPhone carrier) does is that they instruct Apple to update the record on their activation server to say your phone should be getting a "fully unlocked" response. Next time you tether the phone to iTunes it checks the activation token and unlocks the phone.
The best people to answer this is probably someone from the Dev-Team.
Hence the 'Successfully unlocked' message when you restore an unlocked phone.