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.