As previously posted, it does increase when you are talking about TRUE airspeed, but not when you are talking about indicated airspeed. Here's why:
First, stall speed is the speed at which the aircraft stalls under a given set of conditions, so let's nail down the conditions that we are concerned with first. For this discussion we will be considering aircraft flying in straight and level, unaccelerated flight. The only variable we will change is altitude.
Let's look at straight and level flight at a low altitude first. In all straight and level flight (regardless of altitude) the force that balances the weight of the aircraft is called LIFT. Lift is calculated via the following formula:
L=1/2 CsubL rho V^2 S.
Here are what the terms mean:
L: Lift
CsubL: the coefficient of lift. Normally this is written as a C with a subscripted L next to it, but this browser doesn't seem to allow subscripts. CsubL is a dimensionless number that describes the lifting properties of the airfoil, wing, or airplane, etc. It is based on a number of factors, but two of the most important are the shape and the angle of attack of the wing. CsubL increases as angle of attack increases, until you get to a maximum angle of attack, called the stall angle of attack or critical angle of attack, at which point it drops of suddenly. This is a stall.
rho: The greek letter rho (which looks like a squiggly p) is the symbol for air density.
V^2: V stands for velocity, and it is measured as TRUE airspeed. This speed is squared in the lift equation (multiplied by itself).
S: Surface area of the wing. In this discussion we will treat this term as constant, and ignore devices like slots, flaps, slats, and others that can actually change the size of the wing.
Back to the Lift Equation:
So we see from the equation above that there are only two terms that pilots can control, the velocity and the coefficient of lift. Pilots control the velocity by speeding up or slowing down, and they control the CsubL by changing the angle of attack of the aircraft. A greater angle of attack yeilds a greater CsubL, until you reach the stall angle of attack. This means that regardless of altitude, a particular wing has a maximum angle of attack at which it will produce lift, and it will have the maximum CsubL at this angle of attack. This is the angle of attack the wing will always be at when it is at it's stall speed. ALWAYS.
So what happens when we change altitude?
First imagine we are flying at a low altitude at our stall speed. Lift equals weight, and CsubL is at its maximum, because the wing is at it's critical angle of attack.
Now imagine that we start a climb to a high altitude and try to slow again to our stall speed. What happens? Well, when we change altitude, density (rho) decreases. Since it decreases, lift would decrease if we kept everything else the same. In order to fly straight and level, however, lift MUST equal weight, so therefore something has to get bigger to compensate for the decrease in density.
Since CsubL was already at it's maximum, we can't increase it any more, so the only term left that we can increase is velocity. For this reason, it takes a greater velocity (TRUE AIRSPEED) to fly at a higher altitude. Or another way of saying it is that an aircraft will stall at a higher true airspeed at a high altitude than it will at a low altitude.
So that covers TRUE AIRSPEED, but what about INDICATED AIRSPEED?
True airspeed is a measure of how fast the airplane is moving compared to the air molecules that it is flying through. INDICATED airspeed is an indirect measure of the speed of the aircraft. It works by measuring the force of the air molecules being shoved down the pitot tube.
Indicated airspeed is greatly affected by the density of the air that you are flying through, so at a lesser density it takes a higher true airspeed to register the same airspeed on the airspeed indicator. That is an important concept! As you increase altitude, the same indicated airspeed equals a greater and greater true airspeed all because of the change in density of the air.
So what about stall speed? Well as it turns out, even though the TRUE AIRSPEED at which the aircraft stalls will increase as altitude increases (due to changing density), the airspeed that you read on the airspeed indicator (indicated airspeed) will be absolutely independent of altitude. It will stay the same. Or in other words, as long as nothing else changes (weight, bank angle, G-loading, etc.) altitude has no effect on INDICATED stall speed.