Carrier locked means the phone can't use any other SIM card aside from those that are from that Carrier. Carrier unlocked simply means the opposite - any SIM (of the correct size) can be used - though the term "unlocked" suggests that the device was locked before and was subsequently unlocked.
Now, carriers usually pre-load things into the device, such as custom settings or apps. This means that if an update is released by Microsoft, the carrier may want to customize that update as well. In effect, most of the phones that are carrier-locked receive OS and firmware updates much later than those that were not locked.