Hi,
coming back to the point that RyanT mentioned, about the location of bubble formation: the underlying reason is that liquids have significant internal cohesion. In order for a bubble to form, not only there must be supersaturation so that free gas could exist, but there also needs to be "room" (as most liquids are basically incompressible, even at the bottom of the deepest ocean trenches the water is only a few percent denser than at the surface). This "room" of course is the bubble. Growing a bubble once a tiny "room" is there is comparatively easy. Gas can diffuse into the bubble, and ambient pressure drop leads to expansion. But making the initial "room" (the nucleus) is decidedly not, because of the comparatively large intermolecular forces. It is of course possible that this would happen inside the liquid itself, if inert gas supersaturation and ambient pressure drop were really huge. But just think of how relatively easy it is to significantly superheat water, without forming gas. So easy that it is a real risk in some applications. It turns out, that in diving such huge differentials are normally never reached.
But here comes some cool observation everyone can do: Next time you see champaigne (or coke) bubbling inside a glass, look closely WHERE the bubbles are coming from. Most of them not from somewhere inside the liquid, but from surfaces of the glass that are in contact with the liquid! This is actually the other process that is often discussed for forming bubble in divers: "heterogeneous" nucleation at surfaces in contact with liquids. And of course, coming back to tribonucleation, muscle power makes it quite easy to create huge local pressure differences in the liquid, "breaking" it and thus nucleating bubbles...
Hope this helps!