Why does the Coarse-grained Entropy increase?
The probability density $\rho(p(t),q(t))$ of an Hamiltonian system follows Liouville's equation:
$$\frac{d\rho}{dt}=0 \tag{1}\label{1}$$
The intuitive interpretation of \ref{1} is that the probability density evolves in phase space like an incompressible fluid: it can stretch and deform, but its volume in phase space remains constant (figure below, from Wikipedia, shows a 1D example).
This means that if you define the entropy $S$ as
$$S=-\int \rho \ln(\rho) \ dp dq$$
Then $S$ is a conserved quantity:
$$\frac {dS} {dt} = 0$$
The solution proposed by Gibbs is that $\rho$ is actually coarse grained. This means that there is a maximum amount of "stretching" $\rho$ can undergo: if it is stretched further, the volume it takes in phase space will increase. I tried to sketch a 1D example below: on the left you have a "fine-grained" $\rho$, which follows equation \ref{1}, while on the right you have a coarse-grained $\rho$, which takes more phase space volume as it evolves in time.
The problem with the coarse grained entropy is that it is not clear what is the mechanism that should led to a coarse graining of $\rho$. It could be that phase space itself is quantized, as the Heisenberg uncertainty principle seems to suggest. Or it could be, as suggested by Jaynes (E.T. Jaynes; Gibbs vs Boltzmann Entropies; American Journal of Physics,391,1965), that blurring of entropy simply reflects our loss of knowledge about the system. Blurring can be the mechanism that connects the reversible microscopic dynamics to the irreversible macroscopic dynamics, but at the moment there is no consensus in the scientific community about the exact nature of the blurring mechanism.
I love @valerio answer, but I will give it a shoot with a very intuitive explanation.
Coarse grained entropy is an observer dependent quantity which can be though as measuring the ignorance of the observer about the system (or equivalently, the amount of information that can be extracted from the system). For instance observing a box full of bouncing ideal gas particles, I realistically ignore the exact (micro)state of the system, but I can measure that the macroscopic properties are the thermodynamic quantities (P,T,V,etc.).
Suppose now that something happen to the box. If the process is reversible, new microstates will become possible, but an equal number will become forbidden by the constraints given by the measured thermodynamic quantities. If the process is not reversible, more microstates will become possible with respect to forbidden ones. In effect now there are more possible microstates compatible with (P,T,V,etc.), therefore more entropy.
As a concrete example, think about a box containing white particles on one side and black particles on the other side, with a physical divisor in the middle. The act of removing the divisor imply that (besides velocity, position, etc,) now I'm also ignorant about the color of the balls in a given volume of the box.
In summary, in absence of microscopic measurements our ignorance of the system will go up or at best stay constant.