The CO2 molecules are trying to change phase, but the surrounding liquid exerts a pressure. If you consider a simplified mechanical equilibrium between a gas bubble and surrounding liquids
$$\Delta P \pi R^2 = \sigma 2\pi R$$
where $\sigma$ is the surface tension, you have a relation between bubble size and the pressure gradient between liquid and vapour. In the middle of the bulk liquid, there is just not enough 'generation' of vapour molecules in a small location to achieve a stable bubble. Consider now formation of a bubble on a perfect flat surface on the glass and you'll see that the LHS halves, as the area on which the pressure gradient acts is now a hemisphere, not a sphere.
This is however still not enough (and also perfectly flat surfaces don't really exist, but thats a minor point for an engineer like me). For a real surface, there will be tiny grooves. The bubbles don't form at the sharp points, but inside the tiny cavities inbetween - as the balance of area exposed to the pressure gradient and the achievable surface tension is favourable.
The bubble grows inside these cavitities until it is large enough to sustain a spherical shape, and then flows to the top because of buoyancy.
There is one more big clue about these cavities: Because of the favourable balance of surface forces, they will contain small gas pockets from the start as the liquid is prevented from entering due to the surface tension while wetting (pouring in the champagne) - it would be very hard to effectively evacuate these. These gives perfect nucleation sites.
If you're interested, I recommend having a look at Rohesnows work on nucleate boiling (which is more or less the same phenomenon). Makes boiling some pasta seem a lot less trivial.