Why exactly does precipitation occur?
Short story

Maybe it will help to think first about a ridiculous case. Say you have a large hydrophilic solid, and a small drop of water is added on top. We would  not expect the entire solid to disappear into the liquid. Yes, there will be some adsorption and solubility here, yet most of the solid will remain undisturbed. In some sense, the solid 'does not fit' into the liquid droplet over a certain limit.

Similar things are true,  again in a certain interpretation, for more realistic situations. What does this 'fitting' mean exactly? It definitely does not mean there is not enough physical space per se. Instead as you increase the concentration of your solute, the distances between solute entities starts to decrease on average. Hence, at a certain radii the intermolecular forces become strong enough to pull the solutes together. There is often some energy barrier to this approaching, as colloid chemists will tell you, but if the end result is some energy minimum, the process will occur at some rate. 

If the ratio of the amount of solvent to the amount of solute increases, that is we add more solvent, we should expect the solubility to increase. This is indeed what we observe. In summary, the amount of 'space' with respect to solubility is a function of the strength of intermolecular forces and the amount of solvent, among other things. Here you might also discover yourself that smaller particles dissolve more (not only faster!) than bigger particles.

You may compare precipitation to condensation of water in air. There is plenty of actual physical space to go around but once a certain limit is crossed (the dew point) the water will become liquid. Nitrogen and oxygen will not condense at these temperatures since their intermolecular forces are much weaker.[a]

An equally short story

Note first that for $\Delta_\pu{r} G \leq 0$ ($\Delta G$ was poor notation on my part) to be the criterion (necessary and sufficient) of spontaneity, some five conditions must be met: constant temperature, no pressure change, only expansion work is done, and the application of the thermodynamic limit. Fifthly, only one chemical reaction is assumed to take place.[b] Provided these prerequisites stand, we may look at the terms in 

$$\Delta_\pu{r} H-T\Delta_\pu{r} S\le0.$$

(We should not really compare entropy directly to enthalpy because they have different dimensions.) Jumping in quickly, we might say immediately that if the solute can wriggle around more in a solution than in a solid, then certainly $\Delta_\pu{r} S&gt;0$ for the transition $\text{solid}\to\text{solute}$. The only thing standing in our way is that damned enthalpy! Sure enough, that may be the case for some solutions but it is not the whole picture.

Since the solute entities have a solvent layer in solution, there is an entropy effect for the solvent as well. If the solvent is tightly bound to the solute, entropy decreases for this solvent entity. There is also an enthalpy contribution from solvation, not only from the act of breaking or forming bonds in a solid. I would not really dare to generalise which is the bigger contributor 'for most cases'. In general,

\begin{align}
\Delta_\pu{r} H_{\pu{solid to ideal gas}} &amp; + \Delta_\pu{r} H_{\pu{breaking bonds in solvent}} + \Delta_\pu{r} H_{\pu{solute forming bonds with solvent}}\ + \\ &amp;+ \Delta_\pu{r} H_{\pu{residual}} - T\cdot(\text{corresponding ‘entropy’ terms}) \le 0
\end{align}

where 'residual' signals the  solute-solute interactions in the solution.

A sentence or two on $K_{\pu{sp}}$ (with concentrations)

From the IUPAC Gold Book,


  solubility
  
  The analytical composition of a saturated solution, expressed in terms of the proportion of a designated solute in a designated solvent, is the solubility of that solute. The solubility may be expressed as a concentration, molality, mole fraction, mole ratio, etc.


As pointed out by Nicolau Saker Neto in a comment, we should not overemphasise the role of $K_{\pu{sp}}$ in determining solubility. Again there are cases where it is a good indicator, and situations where it fails poorly. There are assumptions which must be satisfied:


there actully exists an equilibrium $$\ce{AB(sln) &lt;=&gt; A+(sln) + B+(sln),}$$ that is not all of the solute "molecules" are dissociated, not really the case for strong electrolytes in a dilute solution,
that the simpification of $a \approx c$ is good enough ($a$ is activity, $c$ is some type of concentration),
provided that the above holds, the concentration of $\ce{AB(aq)}$ should be constant wrt additon of another electrolyte (in some calculations).


If these do not hold, $K_{\pu{sp}}$ (with concentrations alone) is a poor approximation for true solubility. See Denbigh, K. G. 'The Theory of Solubility Product'. J. Chem. Educ., 1941, 18 (3), 126. DOI: 10.1021/ed018p126.



[a] I have largely ignored the discussion of surface energies and surface tension, and how the interaction is often more favourable in the bulk than on the surface, and the fact that $r^3$ grows faster than $r^2$, except for small $r$ when it does not, and hence we need some seeds or nuclei to start the process, and supersaturation, and how particle sizes change etc. The example of smaller particles dissolving more is, of course, a surface tension effect.

[b] In the thermodynamic limit, the general condition of spontaneity comes from Clausius inequality. This is written as

$$\small{T\pu{d}S \ge \delta q.}$$

With the first law of thermodynamics, this is equivalent to

$$\small{T\pu{d}S\ge\pu{d}U-\delta w}$$

or

$$\small{-(\pu{d}U +p\pu{d}V - T\pu{d}S)\ge-\delta w(\text {other})}.$$

With constant temperature and pressure,

$$\small{\pu{d}(U +pV - TS)\le\delta w(\text {other})}.$$

Finally, if only expansion work is done,

$$\small{\Delta_\pu{r} G\le 0}$$

where $\small{\Delta_\pu{r} \equiv \partial / \partial \xi}$; $\small{\xi}$ is the extent of a reaction. The last result also assumes only one reaction takes place, otherwise it is no longer a necessary–sufficient condition for spontaneity.