How fast would something need to travel for this to occur?
When a propeller, usually in a static (no forward motion) situation, spins so fast that it stalls, that stall is sometimes mistakenly called cavitation, but the technical meaning of cavitation refers to liquids where some of the liquid has been turned into a gas.
But doesn't cavitation in water cause a near-vacuum? Why couldn't this be caused in air?
No, cavitation is when the pressure in a liquid gets low enough, typically due to an object passing through, that is falls below the vapor pressure of the liquid and it locally evaporates, causing bubbles of the gaseous version of that substance to form in the middle of the liquid. For obvious reasons, this cannot happen in a flow that is already entirely composed of gas.
A gas can certainly end up with a pressure so low that it becomes rarefied, but it can't have a phase change as a results of locally lowered pressure due to the flow conditions like a liquid can.
There is a phenomenon in air that is sort of the opposite effect, though. Sometimes, when the pressure drops in an air flow and the air is humid enough, the temperature accompanying that pressure drop can get low enough that it falls below the local dew point. In those cases, you can actually get condensation of the water vapor and a sort of cloud will form. This is precisely what happens at the tips of the wings of an airplane when it is taking off or landing on a humid day. That example is due to the wingtip vortices, whose cores rotate at a very high rate and have a correspondingly low pressure and temperature.
Separate names with a comma.