I realised, reading another Phys.SE question about balloons moving forwards in an accelerating car that I don't really understand how buoyancy works. Particularly concerning, for a SCUBA diver.
The top answers to that question seem to claim that balloons get their "sense of down" from a pressure differential. They continue: when a car accelerates, the air at the back of the car becomes more dense, and at the front less dense, changing the plane of the pressure differential and so also, the balloon's sense of up. I find that extremely hard to credit. However, I realised that I don't really know why less dense things float in more dense things.
I'm fairly sure it's something to do with displacement of heavier things by lighter things, and I think pressure acting on the lighter thing's surface has something to do with it, but that's about it.
Best Answer
Basic idea
Picture in your mind a deep ocean of water. Imagine a column of the water, going from the surface down to a depth $d$. That column of water has some weight $W$. Therefore, there is a downward force of magnitude $W$ on that column of water. However, you know the column of water is not accelerating, so there must be an upward force of magnitude $W$ pushing on that column. The only thing underneath the column is more water. Therefore, the water at depth $d$ must be pushing up with force $W$. This is the essence of buoyancy. Now let's do details.
Details
The weight $W$ of a column of water of cross-sectional area $A$ and height $d$ is
$$W(d) = A d \rho_{\text{water}}$$
where $\rho_{\text{water}}$ is the density of water. This means that the pressure of water at depth $d$ is
$$P(d) = W(d)/A = d \rho_{\text{water}}.$$
Now suppose you put an object with cross sectional area $A$ and height $h$ in the water. There are three forces on that object:
Suppose the bottom of the object is at depth $d$. Then the top of the object is at depth $d-h$. Using our results from before, we have
$$F_{\text{below}} = P(d)A=d \rho_{\text{water}} A $$
$$F_{\text{above}}=P(d-h)A=(d-h)A\rho_{\text{water}}$$
If the object is in equilibrium, it is not accelerating, so all of the forces must balance:
$\begin{eqnarray} W + F_{\text{above}} &=& F_{\text{below}} \\ W + (d-h) \rho_{\text{water}} A &=& d \rho_{\text{water}} A \\ W &=& h A \rho_{\text{water}} \\ W &=& V \rho_{\text{water}} \end{eqnarray}$
where in the last line we defined the object's volume as $V\equiv h A$. This says that the condition for equilibrium is that the weight of the object must be equal to its volume times the density of water. In other words, the object must displace an amount of water which has the same weight as the object. This is the usual law of buoyancy.
From this description I believe you can extend to the case of air instead of water, and horizontal instead of vertical pressure gradient.