The pressure differential at a given depth is due to the difference in density at the top and bottom of the float.
No, it's more like in a pile of paper: The pressure is due to the weight of the paper above a specific height (per unit area).
I presume that a compressible liquid causes flotation because there are more molecules striking the underside of the object than the top.
Even in an incompressible liquid, the pressure rises with depth. In the most simple case, pressure rises linearly with depth (ignoring varying gravitation etc.).
Hence the force that the liquid exerts on the surface of a body also increases with depth. More precisely, the pressure in a small area is the component of the force that acts perpendicular to the surface divided by the surface area.
The other way round, force exertet on a particular part of the surface of the body is pressure multiplied by that area (in a linear approximation) or pressure integrated over that area.
For example, the pressure (or force per unit area) on a box looks like:
↓↓↓↓
→ |----| ←
→ → | | ← ←
→ → → |----| ← ← ←
↑↑↑↑
↑↑↑↑
↑↑↑↑
The total force is just the integral over the complete surface area:
The left-to-right and right-to-left forces are balanced, so no net force acts in the horizontal direction.
But the upwards force is larger than the downward force because the pressure deeper down is higher.
Now take a body of the same shape but filled with liquid of the same kind. The body will have a force downwards due to its weight, and a calculation shows that this force is exactly the same (but opposite direction) than the forces on a submerged body of the same shape.
From a comment:
How does the distant mass cause a pressure at the point I measure, if it's not through some compression in the fluid
To build up pressure you don't need compressibility:
Take a column of water of height $h$ and area $A$ throughout its height (like a prisma or a cylinder). If the fluid is non-compressible, then it's mass per unit volume $\varrho$ is constant. The volume of the column is $V=A\cdot h$, hence its mass is $$m=V\cdot\varrho = A\cdot h \cdot \varrho$$ and thus its weight is $F = m\cdot g$ where the gravitational acceleration $g$ is assumed to be constant.
In order to support that column, you need an upward force of $F$, and when you distribute $F$ evenly over the base area $A$, you'll get a pressure of
$$
p = \frac FA = \frac{A\cdot h \cdot \varrho\cdot g}A = g\varrho h
$$
As $g$ and $\varrho$ are constants, the pressure $p$ goes linearly with $h$.
As it appreas, you assume that incompressiblity implies no pressure in the liquid, which would imply that you don't need a force to support a column of fluid; and I have no idea how you come to that conclusion.
Note: With compressible fluids the resoning is basically the same, it's just that $\varrho = \varrho(h)$ is a function of depth $h$. To get the mass of the column above, you'll have to integrate over $\varrho(h)$ which no more simplifies to a nice product:
$$
p(h)=g \int_0^h \varrho(h)\,dh
$$