Actually, leaning (from full rich) will, when at altitude, actually increase the power output. The ideal air-fuel mixture ratio is roughly 14 to 1. Either more or less air for a given amount of fuel will reduce the power output and beyond a certain point will even make the engine run rough, or even quit.
There are two basic ways to see the results of mixture adjustment. One is by an RPM change -- more power equals higher RPM. However with a constant speed propeller, the prop governor would hide the change (though a manifold pressure gauge might show a slight change). The most effective way is through the use of an Exhaust Gas Temperature (EGT) gauge. You lean for highest temperature then, depending on the specific engine, go slightly rich of max (25º C, or so) for best power, or slightly lean of peak for best economy.
When operating in the high country, you must lean your mixture before takeoff, else you'll add quite a bit to the takeoff run, and may even carbon up the engine.
Above about 7500-8000 feet (depending on the aircraft) you'll get 75% or less of max power as the maximum attainable with everything forward. By the time you get to 11,00 or 12,000 ft you may only be able to get 60% or so of max power -- and these figures are based on leaning properly, othewise you get even less.
I might note that the typical pilot who flies from sea level (or nearly) airports won't notice a LOT of difference from leaning on the ground, though he'll see some difference at cruise altitude (and longer engine life), but someone operating from the high country (Denver is a bit over 5,000, Leadville, CO is just a tad under 10,000 ft) will see a marked difference -- it can even be a safety issue.