Let's look at it from the standpoint of design. In particular, let's start with the cruise-flight design condition.
At high altitudes the air is thin (lower density than at sea level) and cold (lower temperature than at sea level). The first causes a loss of engine power, the second causes a reduction in the speed of sound (approx. -14% from sea level to airliner flight levels). The first can be overcome by supercharging (especially with two-speed superchargers) to "maintain" sea-level power at altitude (give-or-take). This power works against the aerodynamic drag of the airplane which is a function of dynamic pressure, that is, at higher altitude in thinner air the airplane can "go faster" (CAS/EAS) on the same power. In other words, with "given" power, TAS increases with altitude (approx. +2% per thousand feet at lower altitudes, decreasing with altitude).
The TAS increase conspires with the decreasing speed of sound at cold temperatures to manifest as a mach number increase with altitude which is disproportionate to the TAS increase alone. That is, mach number goes up faster than TAS. Jet pilots know this by (in part) the transition from IAS airspeed limitations to mach number limitations at high altitudes.
Propellers are limited to tip speeds that are less than some high subsonic mach number (e.g. 0.92M). The increased TAS at altitude increases the helical velocity of the propeller tip, but reducing the RPM of the propeller can counter that trend. Thus, low propeller RPM is important to high altitude, high speed flight. Additionally, a propeller designed for this high altitude cruise condition will have a slightly smaller diameter than a sea-level prop, again in an affort to limit the tip mach number.
So, we've "designed" a propeller optimized for high altitude, high speed flight.
However, a propeller designed for such conditions is not optimal for takeoff and climb conditions. A compromise (since variable diameter is not an option) is to allow that small-diameter high-altitude prop to spin up to near its limiting tip mach number RPM during low altitude and/or low speed operations. Since air is warmer at lower altitudes, the speed of sound is faster. Since takeoff and climb are usually conducted at speeds slower than cruise speed, the helical tip speed can't approach the limiting mach number of the "little" prop unless the RPM is allowed to be significantly higher than the high altitude cruise RPM. This may require that the engine be operated above its design RPM limits, thus a modification to the engine's (existing) reduction gear is required that will permit higher prop RPM without overspeeding the engine. Presuming that the engine we've been talking about all along already had a one-speed gearbox (optimized for the high-altitude design condition), we've just specified a two-speed gearbox.
Said differently and cast in terms of starting with existing low- to mid-altitude technology, the "normal" engine already having a gear reduction and turbo- and/or super-charging (big WWII-era 'V' or Radial engine) needs to have a slightly lower first gear ratio (less reduction since the prop will be smaller than "standard") and a second gear added that has a higher gear ratio (more redution) for high-altitude high-speed cruise operation.
Notice that at no point in the foregoing discussion was the propeller pitch mentioned, nor was any mention given to how much power the propeller absorbed. For the purposes of the foregoing it is assumed that the engine makes the same horsepower at takeoff, climb, and cruise. The constant-speed (actually, constant RPM) action of the governer+prop pitch change will act to absorb watever power that is. In fact, the takeoff power is usually more than the climb power which, in turn, is usually more than the cruise power. However, the range of power absorption capability of a propeller that is well matched to the engine and mission will encompass those power differences and we need not dwell on the issue.
Finally, we have to acknowledge that the free-turbine turboprop effectively eliminates the need for a two-speed gearbox since the power turbine can be designed to accomodate a range of operating RPMs that encompass the range of anticipated propeller RPMs between sea level and mid- to high- altitudes using a single-speed gearbox (see DH8D/Q400, C130J, TU-95, A400M) and the prop governor selects the prop RPM without concern for the internal engine RPM. Further, the advent of the jet engine killed the need for further development of two-speed gearing altogether for about 50 years, and the development of the turboprop in the interim sealed its fate. However, contrary to Piper106's speculation that it was "a bridge too far," I think it was close to operational. It wasn't needed for maritime patrol aircraft (low altitude) and it was supplanted by jets in the altitude stratum for which it was needed (B-36, B-50).
Disclaimer: Everything above could be wrong.
P.S. Why do the P-51s in the WW2Aircraft.net banner art have their flaps down?