Understanding simulated annealing information theoretically
Along the lines of entropy, what you are trying to get to when using Metropolis or Simulated Annealing is a low entropy state.  You want to find order within the disorder.  Now, Metropolis and Simulated Annealing are slightly different things.  Metropolis' goal is not to find the absolute minimum entropy, it is to recreate a distribution, which may be single mode.  What simulated annealing does is focus the Metropolis to find the absolute minimum.
So in annealing you start at a high temperature, which means basically that anything is possible.  Think of quantum tunneling.  The most improbable thing can happen when temperatures are very high.  So when we begin the optimization, we allow for a whole lot of jumps that you would not see otherwise.  As you cool you focus on just what makes sense so that jumps are made only when they are better.
At a high temperature you will accept propositions at a higher rate to test the space and eventually you stop accepting these wacky ideas to focus on the best solutions only.  In the end you should have a good idea of the optimal solution.