Let’s ignore the air, first of all, and put it back later.
When you heat the bottom of the saucepan, the first thing that happens to the water at the top is nothing. It stays cold, because water is not very conductive.
The next thing that happens is that the water at the bottom becomes so hot that it is less dense than the water above it. The first thing that happens then is that nothing happens; the second thing is that the situation is unstable and the tiniest irregularity in the layers makes a blob of less dense water float upwards. The colder denser water sinks to the bottom to replace it, and then is heated in its turn.
(The long thin tube mentioned in the link finds it far harder to convect in this way, which is why the boiling, when it happens, is so explosive).
The rising blob of hotter water can cool by mixing with the water it meets on the way up. Mixing is more or less efficient depending on various things (such as how big the difference of temperature is, and so how buoyant the blob is), so the blob may still be travelling upwards when it hits the surface. Look sideways at a saucepan near to boiling and you will see this.
The boiling point of water is higher at the bottom than at the top, so at a certain moment you will have a blob that is below boiling point when it leaves the bottom finding itself above boiling point when it gets higher up. So boiling can start above the bottom of the vessel in that case; and indeed once a saucepan starts boiling, you see it boiling at the surface and only then does the boiling spread throughout the liquid.
Alternatively the blob may boil on the way up, and the bubble of steam then float up into the cooler layers and condense suddenly. This is the noise a kettle makes when it is near to boiling, and why it goes suddenly quieter when it really starts to boil.
An extra detail: water heated a little above boiling point does not boil. It stays a superheated until some irregularity or impurity acts as a nucleus for the change of state. This is why if you get a saucepan at the late “hot convection” stage and throw salt into it, it fizzes violently. The salt nucleates the superheated water and a bubble of steam forms round each grain.
Now air. Air is less soluble in hot water than in cold, so as the water is heated the air comes out of solution. First, bubbles form nucleated by any roughness of the surface of the base of the pan (if your pan is too shiny, scratch it). Eventually they grow big enough to detach themselves and float to the surface. The air bubbles stir up the liquid they float up through, so that convection happens quicker and in smaller blobs. That is why when you boil already-boiled water the second time, it makes such explosive noises: you get much bigger blobs (because no air bubbles intervene) making bigger steam bubbles which then implode more violently.
Finally, not heating from the bottom. If you grill water, it doesn’t boil at all, it evaporates in a quiet and genteel way. If you microwave water then there is little or no convection and most of it is superheated. This when you take your mug out of the microwave, it is still and innocent and unboiling. When you put a tea-bag into it then its rough surface nucleates the boiling everywhere (like the thrown salt) and you get an eyeful of boiling water.
