Briefly, spontaneous processes tend to proceed from states of low probability to states of higher probability. The higher-probability states tend to be those that can be realized in many different ways.
Entropy is a measure of the number of different ways a state with a particular energy can be realized. Specifically, $$S=k\ln W$$ where $k$ is Boltzmann's constant and $W$ is the number of equivalent ways to distribute energy in the system. If there are many ways to realize a state with a given energy, we say it has high entropy. Often the many ways to realize a high entropy state might be described as "disorder", but the lack of order is beside the point; the state has high entropy because it can be realized in many different ways, not because it's "messy".
Here's an analogy: if energy were money, entropy would be related to the number of different ways of counting it out. For example, there, there are only two ways of counting out two dollars with American paper money (2 1-dollar bills, or 1 two-dollar bill). But there are five ways of counting out two dollars using 50-cent or 25-cent coins (4 50-cent pieces, 3 50-cent pieces and 2 quarters, and so on). You could say that the "entropy" of a system that dealt in coins was higher than that of a system that dealt only in paper money.
Let's look the change in entropy for a reaction $\rm A\rightarrow B$, where A molecules can take on energies that are multiples of 10 energy units, and B molecules can take on energies that are multiples of 5 units.
Suppose that the total energy of the reacting mixture is 20 units. If we have 3 molecules of A, there are 2 ways to distribute our 20 units among energy levels with 0, 10, and 20 units:
If we have 3 molecules of B, there are 4 ways to distribute 20 units among energy levels with 0, 5, 10, 15, and 20 units:
The entropy of B is higher than the entropy of A because there are more ways to distribute the same amount of energy in B than in A. Therefore, $\Delta S$ for the reaction $\rm A\rightarrow B$ will be positive.