You note that you are pretty close to the answer and you are. Let’s assume for a minute (I’m pretty sure the assumption is false, but it’ll get us a good way) that the solubility of the impurity is independent of the amount of desired product dissolved and vice-versa. Let’s also assume we have a mixture of $95~\%$ desired product and $5~\%$ side product which you want to purify by recrystallisation. The desired product has a solubility of $1\,\mathrm{\frac{mol}{l}}$ at $4\,\mathrm{^\circ C}$ and $10\,\mathrm{\frac{mol}{l}}$ at $80\,\mathrm{^\circ C}$; and the side product has the same solubility. And finally, let’s assume that you have $100\,\mathrm{mmol}$ total product (side and desired).
You then add $9.5\,\mathrm{ml}$ of your recrystallisation solvent and heat to $80\,\mathrm{^\circ C}$. That would be enough to dissolve both your $95\,\mathrm{mmol}$ desired product and your $5\,\mathrm{mmol}$ side product. You observe a clear (hopefully boiling because best solubility) solution.*
You then let your solution cool down and put it in the fridge overnight. Due to the decreased temperature, the solubility of both desired product and side product drop. The same volume of solution now dissolves only $9.5\,\mathrm{mmol}$ of both. Since the desired product is supersaturated ($95 > 9.5$), $85.5\,\mathrm{mmol}$ of the desired product will precipitate or crystallise. But the side product is still not supersaturated. We have $5\,\mathrm{mmol}$ of the side product dissolved, but the solvent could dissolve $9.5\,\mathrm{mmol}$. So all of the side product will remain in solution (ideally).
Next step is usually filtration and washing. The filtrate will now contain the saturated product solution which is undersaturated with respect to the side product. The side product didn’t disappear, it merely remained in solution. Wash your pure product, record an NMR spectra and rejoice upon its purity.
Of course, as I stated in the beginning, the assumption that solubilities be independent is wrong. It is also tendencially wrong to assume similar solubilities of desired product and impurity. One would attempt to select a solvent so that the product is not well soluble at low temperatures, but the impurity ideally is. However, the basic principle remains valid: The desired product will form a supersaturated solution and precipitate/crystallise while whichever impurity you have should still be soluble to not co-precipitate.
*: A note on how to do it practically: Usually, you would put your crude product into a flask into an oil bath with a refluxing condenser on top. You would then slowly, dropwise add solvent through the condenser until the solution is boiling and everything is dissolved. One wouldn’t go about saying ‘I should have $x\,\mathrm{mmol}$ so I should need $y\,\mathrm{ml}$ of solvent.’
