AFAIK, Apple's policy is to apply the same carrier lock to a replacement phone as the original phone used to have. So if you have an unlocked phone that needs to be replaced, they should replace it with an unlocked one as well.
Now, it doesn't hurt to remind whoever your are dealing with at Apple of the unlocked status of your phone to make sure that the replacement is unlocked before you leave the counter, especially if it was unlocked some time after purchase.
Although Apple does do repairs/replacements by mail, I strongly recommend going to the closest Apple store and doing it at the Genius Bar. If whoever handles your mail-in request is careless or makes a mistake and sends you locked one instead, it will be difficult to prove otherwise, especially if you no longer have the original phone.
Technically, when a Genius pulls the info for the original phone via SN or IMEI, they get carrier settings on their screen, so they should simply apply the same settings to the IMEI of the replacement phone. However, IMO it is better to verify on the spot.
Actually they don't.
They honor the original sale, e.g. an AT&T locked phone which was subsequently unlocked by AT&T will be replaced by a AT&T locked phone.
You can unlock it again via AT&T.
I had it hapen to me with my IP4, cracked screen, paid $150 for a replacement, i told them in advance that i needed an unlocked phone as replacement, they told me no problem, but after all it was a locked phone which can only be unlocked through AT&T.
With the great help of the apple store, the fact i told them in advance i needed an unlocked phone and proof of unlock by AT&T, i ended up with a brand new factory unlocked 4s!!