When does entropy increase?
Entropy increases when a system increases its disorder.
Basically, a solid is pretty ordered, especially if it is crystalline. Melt it, you get more disorder because molecules can now slide past one another. Dissolve it, and you get another entropy increase, because the solute molecules are now dispersed among solvent.
Order of entropy from least to greatest:
Solid--> Liquid --> Gas