They don't. They fly slower.
Most aerodynamic effects depend on dynamic pressure. More precisely, lift is proportional to dynamic pressure and drag has parasitic component, which is proportional to dynamic pressure, and induced component, which is inversely proportional.
Therefore there is an optimal dynamic pressure at which the aircraft flies most efficiently, and minimal dynamic pressure needed to maintain flight.
Now dynamic pressure is (half of) air density times velocity squared ($q = ½\varrho v^2$) and due to its significance the “indicated airspeed” shown in cockpit actually corresponds to dynamic pressure expressed as equivalent airspeed. All the desired speeds for various phases of flight are referenced to that.
Since cold air is denser, the same dynamic pressure will occur at lower velocity, and because the pilot will maintain the same indicated airspeed, they will actually fly slower.
One more thing: the maximum speed is one of the few exceptions that is not dependent on the dynamic pressure. There are three effects that may limit maximum speed:
Aeroelastic flutter depends on true airspeed (velocity), so the temperature does not, actually, have an effect on it. However because true airspeed is not usually indicated in cockpit, the pilots will use tabulated indicated airspeed values and since these are only tabulated for altitude, they will actually fly slower.
Mach tuck i.e. loss of lift, accompanied with undesirable change in trim, due to exceeding critical Mach number. Since speed of sound increases with temperature, critical Mach number corresponds to lower true airspeed (velocity) in colder weather, so they'll fly slower again.
Engine power. Engines are able to produce more power in colder weather due to being able to achieve higher mass flow with the higher density air. However, engine power is limiting factor mainly for smaller general aviation aircraft, which have low power engines, or fighters at the other end of the performance spectrum, which are designed to fly supersonic and resist flutter. But transport category aircraft generally hit the other two limits first.
Original answer for the version before the reason they fly at higher altitude was explicitly excluded from the question:
There are two, distinct, effects:
Aircraft fly faster at high altitude due to the lower air density. This is because both lift and drag are proportional to air density. So at higher altitude, the plane both have to fly faster to generate enough lift, and can do it because the drag is lower.
More precisely, lift is proportional to dynamic pressure and drag has parasitic component, which is proportional to dynamic pressure, and induced component, which is inversely proportional.
Therefore there is optimal value of dynamic pressure where the drag is lowest. The optimal cruise speed is slightly above this point. Since dynamic pressure is proportional to density and square of speed, the same dynamic pressure corresponds to higher true airspeed at higher altitude.
Dynamic pressure is usually expressed as equivalent airspeed, which is the speed to which current dynamic pressure would correspond at sea level. The indicated airspeed shown on the instruments is approximation of this value.
Heat engines are more efficient at lower temperatures. This is because efficiency of a heat engine (applies equally to both piston and turbine engines and both internal combustion and external combustion (steam) ones) depends on the ratio of temperature, but the combustion increases the temperature by the same (approximately) difference. So if the starting temperature is lower, the ratio is higher and the engines produce slightly more power for the same fuel flow.
Additionally, the maximum temperature is often limited by what the materials can withstand, so at higher altitude the engine can be operated at higher power (well, not really; the power is also proportional to the density, but the engine will again run more efficiently).