I know that if the sun stopped shining, Earth would lose it's heat and we'd all freeze and die. On the other hand, we don't keep increasing temperature when the sun shines because heat escapes to space. But how does the heat leave earth's atmosphere if space is a vacuum and vacuums don't conduct heat except through waves?
How does Earth's heat escape to space?
TL;DR: By the exact same method heat from the Sun escapes into space. Electromagnetic radiation does not require a medium. In fact, electromagnetic radiation works best in a vacuum; no medium is required. Intervening matter has an annoying tendency to absorb electromagnetic radiation. That absorption, in a nutshell, is the greenhouse gas effect.
Earth's heat escapes into space via a complex set of processes. One is convection. Eagles, hawks, and other birds use those rising thermals to get a free ride to altitude. A second mechanism is latent heat. Evaporation of water is an endothermic process, meaning it absorbs energy from the surroundings (this is why sweating keeps you cool). Condensation is an exothermic process. While falling rain cools the surface, the net transfer is upward.
Those rising columns of warm air can only go so high; they only rarely cross the tropopause (the boundary between the troposphere and stratosphere), and that is only in the case extremely unstable of conditions. Latent heat, along with birds, ride those rising columns of air. This brings up a third and the ultimate mechanism by which the Earth's heat escapes into space, which is electromagnetic radiation.
Every object, including the Earth's surface, absorbs and radiates heat electromagnetically. The atmosphere does the same. The atmosphere absorbs most of the electromagnetic radiation emitted by the Earth's surface. (I qualified that with "most" because there is a small window in the thermal infrared that goes directly into space, at least when there aren't clouds.) This absorbed radiation is quickly re-emitted as thermal radiation, but in a random direction.
The heat carried upward by thermals, by latent heat, and by surface radiation eventually does make its way into space as electromagnetic radiation.
Through radiation, which doesn't require matter to transfer heat. Here is a good explanation: How Does Heat Travel?
The answer, as already given is "By radiation" . But comments and other answer detail have added extra information which can be useful in understanding this in the wider context, particularly relating to arguments about the Earth's energy budget and climate change. Here is some other extra stuff to consider; We pose the same question for the planet Venus. Venus has an atmosphere composed of nearly pure CO2 (actually about 96.5%). The surface temperature on Venus is around 750K at the equator when facing the sun and drops by a mere 5K overnight. Night and day are about 120 earth days in length so that's a pretty slow axial rotation and a very slow loss of surface heat during the planet's night. Now the atmosphere on Venus is very thick, masses of that lovely CO2, and surface pressure is about 90 times that of earth (9.2MPa). If you calculate the optical attenuation of the atmosphere to incoming solar radiation then the solar flux at the surface is a mere 4W per sq m. It is therefore self evident with such a low solar flux at the surface that the direct radiation from the sun cannot warm the surface to 750K. It is therefore interesting to draw some energy flux diagrams (similar to the Trenberth ones for the earth) and calculate the source of all that extra heat warming the surface. Don't forget to draw 2 diagrams, one for night and one for day to check you understand how a pure CO2 atmosphere works.
This is a great exercise for school students (and anybody else) interested in the greenhouse effect of CO2.