Why does increasing the temperature of a *solid* increase its entropy?
All right, someone bearing the standard of thermodynamics will give you the equations shortly... From a layman to another, here goes my attempt at a simpler explanation.

Entropy may be seen as the "disorderlyness" in some settings, but that is not a very useful way of seeing it. The metaphor is often used, but creates the wrong conclusions when looking closer at it. To me, is best to look at it as a quantity closely related to the number of possible (different) states available to a certain system. It is then obvious that if you increase the temperature, more modes of vibration are available, thus more states, ergo more entropy. The more stuff is in your room,  the less probable is the state where everything is ordered - if all states are equal in probability ;)