There are two main points to your situations.
1. Does the lock should know how to unlock itself ?
There are basically two kinds of "signature" systems, and only one of them is really a signature. In your situation, the server will send to the device some sort of token which the device will verify. So the question is: is it a problem if the device would have the technical power of producing a valid token ? Or should things be such that the device contains nothing which would allow it to make such new tokens ?
In the former case, you can work with a MAC, and HMAC/SHA-256 is not a bad choice for that. However, this means that the device and the server share some secret key, which is used to both produce and verify unlock tokens. If there are several devices, then each should have its own device-specific key, and the server should then know all device keys -- otherwise, ripping apart one device would allow an attacker to learn enough to unlock all other devices.
In the latter case, the server has an asymmetric key pair; unlock tokens are signed with the server's private key, and devices verify tokens with the server's public key. RSA is a popular digital signature algorithm; the verification part is inexpensive, and thus can be performed by most devices, even power-limited devices.
2. What about replay attacks ?
A "replay attack" is, in your case, when an attacker observes an unlock token, and sends it again at some later point. There are several ways to avoid such issues, but they all imply some sort of extra capability on the device:
Time-limited tokens. The token includes an issuance date and the device won't accept a token which is "too old". This method requires the device to have a reasonably accurate embedded clock.
Duplicate tracking. The device remembers previously seen unlock tokens, and refuses to act upon a token which it has already seen. This requires some sort of memory which cannot be reset.
Nonces. The device first emits a random value, and expects the unlock token to contain a copy of that specific value. This makes the protocol more complex and requires the device to be able to emit data as well as receiving tokens. This will not map well to all situations; for instance, if the device is a door lock, with a keypad, and the user contacts the server through his smartphone. Typically, the device would need a small LCD screen to display its nonce.
You may want to consider HOTP: this is a MAC-based protocol, thus with a key shared between "server" and "device". Both server and device remember only a short counter value (say, 32 bits) and this is sufficient to protect against replay attacks. The communication is one-way (the device needs not emit anything). This protocol (or any similar variant) is what is used to unlock your car: the car is the "device" and the remote control attached to the key ring is the "server".
All of the above is about the token sent from server to device. Of course, the server should not produce the token unless it has good assurance that it is token to the right user (the device owner). You thus need authentication which, in practice, will mean SSL. Let the user open a SSL connection with the server (say HTTPS) and authenticate with the server. The SSL layer will take care of integrity and encryption so you do not have to encrypt the token itself. Actually, encryption would not be needed for an unlock token at all -- you may want to use encryption only to deter eavesdroppers, and you want to thwart eavesdroppers only if your token-verification protocol is weak against replay attacks. In any case, encryption is best left to a layer where all the tricky details have been smoothed out through years of teeth cringing toil, and that's SSL.