There are two distinct notions of entropy that show up in thermodynamics, one from thermodynamics itself and the other from statistical mechanics. These different notions end up being equivalent (surprisingly enough), but conceptually the statistical notion is simpler.
Statistical entropy measures the degeneracy of a system. To see what this means, we need to discuss macrostates and microstates.
Consider a system containing $N$ particles, which is split into two sides, left and right. In particular, we consider each particle has having one determining property: which side it is on (for simplicity). We can completely characterize the system by listing, for each particle, which side it is on. This is a microstate: it describes the microscopic behavior of the system.
However, say we are looking at the system from a macroscopic point of view. We cannot see where each particle is, but only can tell how many balls is on each side. Say there are $N_{l}$ on the left and $N_{r}$ on the right.
Note that we can summarize the system with just $N_{r}$ and $N$. The total summary of the system is called the macrostate.
Much of statistical mechanics is about the relationship between microstates and macrostates. Statistical entropy is a particular example of this. For a particular macrostate, it gives information about how many microstates produce that particular macrostate.
The statistical entropy tells us how many ways there are to arrange the $N$ particles such that there are $N_{r}$ on the right hand side. In general, the number of microstate producing a particular macrostate ($N_{r}$) is denoted $W(N_{r})$. Then the statistical entropy is
$$ \sigma(N_{r}) = \ln(W). $$
For our example system, we can precisely determine $W$. The number of ways to have $N_{r}$ particles on the right hand side is
$$ W(N_{r}) = \binom{N}{N_{r}} = \frac{N!}{N_{r}!(N - N_{r})!}. $$
The binomial coefficient $\binom{N}{N_{r}}$ is the number of ways, out of $N$ objects, to select $N_{r}$ of them, ignoring order. If you look at how this $W$ changes with $N_{r}$, you can see that for $N_{r}$ close to either zero or $N$, $W$ is relatively small. That is because these are in a sense very 'special' states, when most of the particles are on one side or another. They have low entropy.
Naturally, this gets more complicated as you move to systems where you have other factors, such as temperature. However, this simplistic example provides motivation for ideas that in general are quite hard to grasp.
For example, the idea that entropy can only increase.
The key is in the relation between the entropy and the likelihood of a macrostate. As entropy increases, the number of ways $W$ to get the macrostate increases. In a system as simple as our example, the probability of a microstate is directly proportional to $W$. This is sometimes referred to as the fundamental postulate of statistical mechanics (although the name sometimes refers to a related, but more general idea).
Then we see that the high entropy (macro)states are simply those which are most likely. Thus, in claiming that entropy always increases, we are saying that the system tends to its most likely states.
However, from our description, we have left open the possibility that entropy 'momentarily' decreases before increasing, fluctuating about in its progression toward the maximum. The reason we can ignore this has to do with the fact that the number of particles $N$ must be very large. For such large $N$, the fluctuation is incredibly small. Thermodynamics just ignores this since it is mostly irrelevant to predicting the behavior of real systems.
The other notion of entropy is the thermodynamic entropy,
$$ S = k_{B}\sigma, $$
where $k_{B}$ is the Boltzmann constant. Now, this is not how its defined, but rather is its relation to the statistical entropy. The thermodynamic entropy is often defined by $dS = \frac{\delta{Q}}{T}$, where $\delta{Q}$ denote heat transfer. This was already nicely discussed in an answer to another question, "Intuitive understanding of the entropy equation". Essentially, the temperature was actually initially defined so that heat cannot flow from cold regions to hot regions. It is just nice and convenient that temperature actually corresponds to what it should.
This is not exactly satisfying, but we can motivate the notion using statistical entropy. In particular, think about the statistical entropy of a gas where the temperature is uniform. The statistical entropy should be higher than for a gas where the temperature is not uniform. In essence, a non-uniform distribution of temperature is more special than the uniform case, and we expect to be able to produce it from fewer microstates as a result.
If the uniform temperature case is the least special, and thus highest entropy, then the increase of entropy implies that the system tends towards uniformity. However, this is just saying that heat flows from hot to cold, removing the temperature difference, rather than cold to hot, which would increase the temperature difference.
I should note that my terminology is not quite standard. Statistical and thermodynamic entropy in particular are nonstandard, as $S$ is typically just entropy (although $\sigma$ is sometimes used as defined). Furthermore, the macrostate of a system usually includes entropy in addition to other determining variables (for example, $N$).