To put it simply, a locked phone has carrier restrictions, which are imposed by means of software locks installed by a particular cell phone carrier (eg. AT&T). This means you can only use it on their network, using their SIM cards (or certain international carriers that they have agreements with if you pay for international voice and/or data services).
An unlocked phone is free from any carrier restrictions, and will accept virtually any SIM card, given that the phone has the sufficient hardware capabilities (network protocols and frequencies) to work on said carrier. Most phones in the world sold at full price are factory unlocked, and you will never have to worry about swapping out a compatible SIM card.
In countries where subsidized cell phones are common, many phones come locked. But under certain conditions, the carrier that sold the phone to you can unlock the phone on request. This is where your question about contracts comes into play. On networks such as AT&T, subsidized phones come locked, and can be unlocked after your contract period has ended. Under most circumstances, once a previously locked phone has been unlocked, it will stay that way for perpetuity,