There's two important differences between air and water: Air is compressible, and the densities are about a factor of ~1000 apart - 1 kg/m³ vs 1 t/m³!
For most concerns where you use propellers, compression plays no role because the pressure diferences are very low. The densities, however play a large role.
The thrust can be described as $F = \dot m * \Delta v$, with $\dot m$ beeing the mass flow - kg&/s or such - and $\Delta v$ the difference in velocity a volumeelement of fluid is accelerated.
So, to achieve a similiar thrust, the same propeller would have to move 1000 times more air than water by volume. Hence the often larger and faster spinning propellers for planes.
On the other hand, in a heavier medium each wing of the propeller is subject to stronger torque (all else beeing equal):
$$Q = \rho V_{a}^2 D^3 f_q(\frac{ND}{V_a})$$
(Source)
$\rho$ is density, $V_a$ rate of advance (how much the propeller moves forward per revolution), D is diameter and N number of revolutions.
Without going into the math it can probably be shown that in a heavier medium the propeller will experience somewhat more torque for the same thrust - I'm to lazy to try now. The propeller will be built with more robust (and possibly heavier) material than would be the case id it's an only air propeller.
That said, I believe that a propeller for both media is entirely possible, though challenging.
However, a propeller for a both media will need a drivetrain that can accomodate speed roughly a factor 1000 apart (that's not trivial).
One other reason why don't see a propeller for both media is that there is no vehicle that could make use of one.