In Canada at least last year, the unlocked phone was sold with a different/specific ICCID (SIM serial number) input at purchase time. The box is the same, but they punch it up differently when you pay for it.

The ICCID is input as a series of 1's which I suppose flags their system for the unlock. So when you connect to iTunes, which then hits Apple's servers, your phone isn't locked to a provider.

The receipt also clearly stated: "No Contract SIM"

Just before buying mine I read stories of people having walked out of the Apple store to find out their phones had actually been locked - the employee had punched in the SIM number instead of 1's - the rest of the receipt was the same, including the unlocked price.

When I bought mine I checked this specifically and even mentioned it to the employee, and she confirmed that a few at that store had also been previously punched in wrong, but that they were being extra attentive to that now.