How can entropy always be increasing, while each microstate (among which low-entropy micro states) is equally likely to occur? The reasoning in my statistical physics book is as follows:
$\cdot$ The basic postulate of Statistical Mechanics is that for a system with a fixed energy, particle number and volume, each microstate is equally likely to occur.
$\cdot$ For a certain physical quantity A, the entropy (and multiplicity) will have a maximum at A* of A. 
$\cdot$ Starting at A different from A*, the system will explore other available states and automatically end up in configurations with the value A*, because a large majority of microstates has a value for A very near A* due to the high multiplicity at A*.
$\cdot$ Conclusion is that a system starting in A will always end up in a state where S has its maximum (at A*)/the entropy always increases if we leave a system alone.
I do not understand that, when the system explores all available states and when every microstate is equally likely to occur, that the entropy necessarily increases all the time. Isn't there a small chance that the system will end up in a state with significantly lower entropy and that it immediately gets in to a high entropy state again after?
 A: Firstly, great question. 
You are correct in saying that the law is inherently probabilistic. Every outcome is equally likely, but there are vastly more states of disorder than there are of order. In terms of coarse-graining regions, the states representing disordered outcomes are much larger than those representing order. Hence, in the evolution of any system, there is an overwhelming likelihood that the system evolves such that entropy increases. 
In theory, there will eventually be an exception to this law. However, that exception would require churning through enough states that, in principle, it will never happen for times up to and well beyond the age of the universe. 
The fact that entropy always increases accounts for the arrow of time we experience. To give you some idea of the rigidity of the Second Law, think in terms of how definitely time moves in one direction, for this is a consequence of the evolution of states according to the Second Law. 
It is interesting to think about the fact that the Second Law accounts for the arrow of time. If this law were to be momentarily broken in the very distant future, would the arrow of time be instantaneously reversed? 
A: 
I do not understand that, when the system explores all available states and when every microstate is equally likely to occur, that the entropy necessarily increases all the time. Isn't there a small chance that the system will end up in a state with significantly lower entropy and that it immediately gets in to a high entropy state again after?

There's a common misconception here: microstates do not have entropy. Entropy is a measure of our ignorance of which microstate a system is in. If we did know the microstate, the entropy would be exactly zero. (This doesn't contradict the common intuition that "entropy is disorder". That happens because a high entropy means many possible microstates, and the vast majority of all microstates look very disordered. So they're related but not exactly the same.)
The two statements in your book aren't contradictory. In equilibrium, entropy is maximized. Accordingly, we have the least possible amount of information about which microstate is occupied, so the probability is uniform.
