Why can the entropy of an isolated system increase?

Take a room and an ice cube as an example. Let's say that the room is the isolated system. The ice will melt and the total entropy inside the room will increase. This may seem like a special case, but it's not. All what I'm really saying is that the room as whole is not at equilibrium meaning that the system is exchanging heat, etc. inside itself increasing entropy. That means that the subsystems of the whole system are increasing their entropy by exchanging heat with each other and since entropy is extensive the system as whole is increasing entropy. The cube and the room will exchange, at any infinitesimal moment, heat $Q$, so the cube will gain entropy $\frac{Q}{T_1}$, where $T_1$ is the temperature of the cube because it gained heat $Q$, and the room will lose entropy $\frac{Q}{T_2}$, where $T_2$ is the temperature of the room because it lost heat $Q$. Since $\frac{1}{T_1}>\frac{1}{T_2}$ the total change in entropy will be positive. This exchange will continue until the temperatures are equal meaning that we have reached equilibrium. If the system is at equilibrium it already has maximum entropy.  

For completeness, an information theoretical answer is needed. Entropy is, after all, defined for arbitrary physical states and does not require a notion of thermal equilibrium, temperature, etc. We need to use the general definition of entropy, which is the amount of information that you lack about the exact physical state of the system given its macroscopic specification.

If you knew everything that is to know about the system then the entropy would be zero and it would remain equal to zero at all times. In reality, you will only know a few parameters of the system and there is then ahuge amount of information that you don't know. Now, this still does not explain why the entropy should increase, because the time evolution of an isolated system is unitary (there is a one to one map between final and initial states). So, naively, you would expect that the entropy should remain constant. To see why this is not (necessarily) the case, let's focus on the free expansion experiment caried out inside a perfectly isolated box. In this thought experiment we make the rather unrealsitic assumption that there is no quantum decoherence, so that we don't smuggle in extra randomness from the environment, forcing us to address the problem instead of hiding it.

So, let's assume that before the free expansion the gas can be in one of N states, and we don't know which of the N states the gas actually is in. The entropy is proportional to Log(N) which is prioportional to the number of bits you need to specify the number N. But this N does not come out of thin air, it is the number of different physical states that we cannot tell apart from what we observe. Then after the gas has expanded there are only N possible final states possible. However, there are a larger number of states that will have the same macroscopic properties as those N states. This is because the total number of physical states has increased enormously. While the gas cannot actually be in any of these additional states, the macroscopic properties of the gas would be similar. So, given only the macroscopic properties of the gas after the free expansion there are now a larger number of exact physical states compatible with it, therefore the entropy will have increased.

While Bubble gave a nice example, let me try to explain this with "Clausius inequality". (You can read this on several sources, I like the explanation from Atkins' Physical Chemistry)

Let's start with the statement: $$ |\delta w_{rev}| \geq |\delta w| \\ $$ Furthermore, for energy leaving the system as work, we can write $$ \rightarrow \delta w - \delta w_{rev} \geq 0 $$ where $\delta w_{rev}$ is the reversible work. The first law states $$ du = \delta q + \delta w = \delta q_{rev} + \delta w_{rev} $$ since the internal energy $u$ is a state function, all paths between two states (reversible or irreversible) lead to the same change in $u$. Let's use the second equation in the first law: $$ \delta w - \delta w_{rev} = \delta q_{rev} - \delta q \geq 0 $$ and therefore $$ \frac{\delta q_{rev}}{T} \geq \frac{\delta q}{T} $$ We know that the change in entropy is: $$ ds = \frac{\delta q_{rev}}{T} $$ We can use the latter equation to state: $$ ds \geq \frac{\delta q}{T} $$ There are alternative expressions for the latter equation. We can introduce a "entropy prodcution" term ($\sigma$). $$ ds = \frac{\delta q_{rev}}{T} + \delta \sigma, ~~\delta \sigma \geq 0 $$ This production accounts for all irreversible changes taking place in our system. For an isolated system, where $\delta q = 0$, it follows: $$ ds \geq 0 \,. $$