From the Wikipedia article about Entropy (Source view via The Internet Archive):
In irreversible heat transfer, heat energy is irreversibly transferred from the higher temperature system to the lower temperature system, and the combined entropy of the systems increases.
If entropy were a measure of disorder, or randomness, or the amount of information needed to describe the microstates of a system, then it seems that when the difference in temperatures is high, entropy should be high. A temperature gradient in the systems is a form of ‘disorder’ hence should be a sign of higher entropy.
So why does entropy increase after the heat transfer, as the combined system approaches a uniform temperature? It seems to me like a state with less randomness or disorder.