Updating device remotely

Let's say you have a small-ish embedded device that communicates with remote server via network connection. It would be nice to update its software remotely, but since it is, well, remote, you generally want that the such updates are as fool-proof as possible. As in, no change (or very marginal one) of bricking the device.

This obviously means that the updates can't be done over active connection. Any issue with said connection might cause your update to be interrupted, causing it to fail and leaving system in unpredictable and likely corrupt state.
Solution for this is to load the software fully to local storage and to verify it against known checksums before starting the update, to make sure that everything is received properly.

Also, you generally do not want to software to perform full self-updates. If software is one monolithic block, any failure during update will easily leave it in corrupt state.
For this, the software must actually be in two parts; first is the bootloader, which in perfect world is immutable and never touched outside device production. And the second part is the main application software that can do everything but to actually perform the update (including downloading and initial verification of it).

The update process, then, is something like this:

• Main application contacts server and receives a notification of update
• Main application downloads update to local, nonvolatile storage reserved specifically for updates.
• Main application verifies that the update is valid, uncorrupt and optionally properly authenticated
• Main application sets nonvolatile system state to "perform update" mode, and starts system again
• Bootloader, on startup, checks system state and notices that update should be done, causing it to branch to update, instead of starting main application as would be normal operation
• Optionally bootloader verifies the update data again, to make sure everything is proper
• Bootloader then loads update data from nonvolatile memory and replaces main application data with the updated version. 
• If this process is interrupted (power loss for example), system is still in update mode and can resume update.
• After update is done, bootloader verifies it once again, and when satisfied that everything is correct, updates system state to normal operating mode and starts main application.

Depending on how far you want to go to make sure everything keeps rolling no matter what, there may also be two copies of software, so you can go back to old version in case new version somehow doesn't work. There is also possibility of encrypting the software when it is in transit, so that only the bootloader can decrypt it during update, to retain secrecy of your code.

Now, if you ever wanted to update the bootloader... Well, it can be done with this setup, too, but generally you don't want to do that, as failure there may be unrecoverable, or at best, difficult to recover from. Generally speaking, though, you want to avoid this as much as possible.

You may notice that I haven't written a word on how to actually implement this stuff. That's right. Every single system is slightly different here, so there isn't single solution for this, and without knowing your exact setup I can't really give any ideas. Other than ones provided above.