How does a Bitcoin client efficiently change forks? Occasionally, a Bitcoin client will come across a fork of blocks that is longer than the chain it is currently on. Depending on how often orphaned blocks occur, this could be quite often. When this happens, any internal data structures relating to the "current" state of the blockchain (for example, a hashtable of unspent outputs) need to be updated to reflect the state of the new, longer fork.

How is this accomplished? Is history played "backwards" to the most recent common ancestor and then "forwards" to the new top block? Is it all just reconstructed from scratch?
The UXTO set certainly isn't reconstructed from scratch, that would be an incredible DoS vector if it did. Even on fast machines a complete reconstruction takes hours, days on slower disks and processors. 

From a look at the source on github, we can see that your assumption is correct. The UXTO set is reconstructed backwards to the point where the chain is forked, and then continues on down it as normal.

The client seems to assume that large (100+) reorganisations of the blocks are improbable, which is why coins need to "mature" to avoid the situation where there's transactions spending coins that no longer exist in the chain.