How do MtGox redeemable codes work? At MtGox (and presumably some other sites), you can withdraw money in the form of a redeemable code. These codes are also accepted for deposit at some Bitcoin exchanges.

How does this work? Specifically, is there protection against double-spending? Can I know that the code I got is still valid, and has not been given to others as well?
The code is effectively just a long random string.  When you create a redeemable code, a random string is selected, entered into the database at the exchange and associated with a currency and an amount.  That string is your redeemable code.  The string is long enough to make it very unlikely that anyone would be able to guess it in a reasonable length of time.

The first person to attempt to redeem the code gets the amount credited to their account on the exchange, which causes the database entry on the exchange for that code to be marked as having been redeemed.

The way to tell whether a code is valid is to try redeeming it.  If it works, you're the first to try it.  If not, you're either not the first to try using it, or it was never a valid code to start with.

The exchange should prevent "double-spending" by making sure that the "look up whether code is spent; credit account; make code as spent" sequence is an atomic operation.  We don't want two users both running through that same sequence at the same time, where both pass the "look up whether code is spent" check, then both accounts get credited, etc.