To pull the Wikipedia info into an answer so we don't send the community site-hopping:
From a classical perspective, temperature is the amount of thermal energy in a system. The absolute Kelvin scale defines zero as a state in which the system has zero energy, and all higher degrees Kelvin are sequentially more energy, with no upper bound. Given this definition, common sense would say that negative absolute temperature is not possible. And, in the scheme of most things, that's the correct viewpoint; you can't remove energy from a system that has none, and you can always add more heat or kinetic energy to a system and increase its temperature, no matter how hot it is.
However, temperature can have another definition, more rigorous than simply the amount of energy, based instead on the relationship between energy and entropy; a change in temperature is the change in total energy, divided by the change in entropy. Entropy is defined simply as the amount of energy inherent in a system that is unavailable for doing work; energy lost to natural disorder. Typically, as energy increases, so does entropy; the Second Law of Thermodynamics states that you can't get the same energy out of a system that you put in, because some is lost to entropy. Stated more simply, the entropy of an energetic system is always rising. By how much depends on the amount of energy in the system as compared to its surroundings. This increase in entropy is modeled by the thermodynamic beta; mathematically the reciprocal of temperature, it is a measure of how much the entropy of a system increases when energy is introduced. For each fixed amount of energy added to a system with no finite upper energy limit, temperature will decrease less, and entropy will increase more. You can see these properties quite simply, by using a torch or other flame to heat a piece of iron. The hotter the metal gets, the harder it is to continue increasing the temperature and the more quickly it wants to cool when the heat source is removed.
Now, consider a hypothetical system that does have an upper limit to the amount of energy it can have. Most systems you could think of off the top of your head do not have this limit, as previously discussed, but we have found a few in the real world that do. Such a system, as energy is added, would want to increase its entropy as any system does; however, as energy continues to be added, the amount of the total energy in the system that can be in entropy decreases.
As an analogy, consider a rigid container. Shake it; you don't hear anything because it's empty. Now, put a few ball bearings into the container, one of which you've colored or otherwise marked. You close the lid and shake the bearings up. The ball bearings rattle around pretty freely, and relatively unpredictably, such that you could not reliably predict exactly where the colored ball bearing is when you open the lid again. Now add more ball bearings, not enough to completely fill the container, and shake again. Each ball bearing has less "room" to rattle around, and so the relative position of any given ball bearing will change less, and thus the colored one will be more predictable as to its position when you go looking for it. Now, keep adding ball bearings, perhaps stirring or shaking the bearings so that they settle and you can put more in, until you've added every last bearing you can fit in the container. Close the lid. Shake. You don't hear anything. The colored bearing stays exactly where you left it. You have reached the absolute upper capacity of the container; not a single extra ball bearing can be fit into it, and so there is nowhere for the existing ball bearings to go. As such, you can predict exactly where the colored ball bearing is; right where you last saw it.
On a quantum level, where the BBs are quanta of energy, this is what's happening in a system with an upper energy bound. As more and more energy is added, all the atoms or other particles in the system approach their highest possible quantum energy state. The number of particles at any lower state decreases, as does the probability that if you were to pick a particle at random, it would be at a state less than the highest energy state. At this point, as energy is added, entropy is decreasing, not increasing as it normally does. We have crossed a threshold; at the point where adding a joule decreases the total entropy, the thermodynamic beta of the system is now negative, and by definition, so is the temperature (the reciprocal of a quantity, which is what temperature is to thermo-beta, can never be of a different sign).
Now, here's the kicker. We just got to negative temperature by adding energy to decrease entropy. Well, as long as this relationship is inverse, the temperature is negative. So, we can also get to negative temperature by removing energy until entropy increases. This is accomplished, in most cases, by forming Bose-Einstein condensates. A Bose condensate is a gas composed of bosons (particles or particle groups with an overall integer spin; helium-4 is a commonly-studied gas meeting this criteria as it has a net zero spin) cooled to near-absolute zero. What we see in this state from many (but not all) Bose condensates is a property called superfluidity; the atoms of the gas have little or no repulsion to each other by electromagnetism, and so "flow" around each other and their surroundings quite liberally (as if they had zero viscosity).
This is a point at which decreasing temperature increases entropy; there is insufficient energy to maintain order among the atoms of the gas, and the material descends into chaos. Classically, we still call this above absolute zero, because the system still has measurable energy (the atoms are moving, therefore there is kinetic energy and thus total energy in the system), but it's a point at which the fundamental ordered structure of matter begins to diverge, and our math can no longer tell us what will happen, because, by our definition of temperature as the reciprocal of thermodynamic beta, zero is a point of divergence in temperature but not in beta. So, we define "absolute zero" as a point at which entropy gain or loss is at exactly zero as energy changes, but energy is still inherent in the system; it is a total disconnect from everything else we know about how energy and entropy are related.