How does freezing water to make ice remove whatever salts were in the water to begin with?
In simple terms, there isn't any space in the ice crystal lattice for the extra atoms and there is no way to plug either of the ions (or the whole salt molecule) into the growing pattern.
So more and more water joins the frozen mass, leaving a more and more concentrated brine until essentially all the water is frozen and the salt remains behind. As Manishearth notes in the comments this requires getting things rather colder than the usual "freezing point" of water.
@MartinBeckett's already gave an excellent answer: Salt is excluded from ice because there is "...no way to plug the ions... into the growing [ice] pattern."
This unusually long answer -- a mini-tutorial really -- is an expansion on his answer. I've added a long background section that uses informal, easily visualized analogies to define a number of related concepts, but the piece is still intended as a direct answer to the question that was asked. The extra background material hopefully makes the answer more memorable, and also makes it possible for me to address some more subtle aspects of the differences between periodicity and randomness.
A Dance of Molecules
The Random Texting Dance
Imagine if you can a crowd of people in some city plaza who are walking rapidly and constantly texting or twitting. (Any resemblance of this to real life is purely coincidental.) They are all so engaged in what they are typing that for the most part they are blissfully unaware of each other's existence, except when they sometimes bump harmlessly into each other.
Let's call this situation the random texting dance, since all that motion makes it a bit like a dance, but one with no particular pattern to it.
Next, let’s further assume that it's the Chinese New Year, and that to celebrate the occasion the city has provided both a number of Dragon Dancers -- a dozen or so people under a long Chinese Dragon costume -- and also a few very well trained Chinese Elephants, ones trained to give way even to highly distracted human texters. (They go in big for Chinese New Year in this city!)
Now here’s a simple question: What will happen when these large and oddly-shaped participants walk right into the middle of the random texting dance?
Well, because everyone is in motions and has room to navigate, the simple answer is that both the Dragons and the Elephants will be accommodated without much trouble. The texters move out of their way and allow them to become parts of the overall random texting dance.
Now in its simplest possible form, the situation I just described can also be thought of in molecular terms. The random dance of the texters plays the role of a solvent, while the two large participants are examples of larger molecules that are can slip into the crowd and become part of the overall dance, even if at a somewhat slower pace.
The Random Square Dance
Now let's look at a second version of the same crowd, one that I'll call the random square dance. In this old-fashioned crowd, no one is texting. In fact, by the rules of this crowd, no one is even allowed to move forward unless they can find and grasp the hand of another dancer, even if only for a few moments. Once they find such a helping hand, both of the dancers can move and change positions within the crowd. That part is like a real square dance, but unlike a real square dance there's no pattern in the overall motion of the crowd.
In some ways, the random texting dance and the random square dance are not all that different. In both cases, individual dancers can move about pretty much at random through the crowd. A video of their motions likely would show rather similar results, with perhaps more turns and pivots in the random square dance.
Some Dances are a Real Gas
However, if you look more closely at the two cases, you find out something a bit surprising: the random texting dance behaves a lot like a gas, while the random square dance looks a lot more like a liquid. To see this difference, you only need to look at what happens when the two dances encounter a big empty space.
In the random texting dance, no one is connected to anyone else. That means that every time one of the dancers encounters the edge of an empty space, she or he will just drift off randomly into it. That's a pretty close equivalent to a gas expanding out into an open container.
In the random square dancing, something starkly different happens. These dancers can only move forward when here are hands for them to grasp, and there are no hands in the big empty space!
The result of this lack of a path forward quickly results in a well-defined boundary at which the dancers can travel no farther. Dancers at this boundary are even pulled a bit more tightly towards the crowd, since they have hands pulling them inward, but no hands pulling them out. That's a different situation from the interior where hands pull equally in all directions. The pull at the boundary also tends to smooth out any bumps, since any person sticking far out will be pulled only back towards the crowd, without any canceling pulls from any other direction.
Put that all together and you have pretty much exactly what happens at the surface of a true liquid: The molecules are required to "lock hands" with other molecules to move forward, so they end up forming a flat, dense, and elastic (bumps and dimples get flattened out) boundary. If you recognize that bonds are bonds no matter what the scale is, the physics of the random square dance crowd really is no different from that of the molecules in a liquid. The presence of such a boundary is the literal definition of the difference between a gas and a liquid, and is why the random texting crowd qualifies not as a liquid, but as a gas.
Chances of Precipitation
Now it’s important to point out that you can dissolve substances in gases just as you can in liquids, and the situations are similar in many ways. However, the terminology changes a bit when you do. For example, water dissolved in air is called "water vapor" instead of "an air solution of water." The amount of water dissolved in air is called the "humidity" of the air, with high humidity just meaning you have more water dissolved in it. And just as liquid water can only hold so much salt before the salt starts precipitating out as crystals, air can only hold so much water before he water starts precipitating out of it as, well... precipitation. (There are many, many details I'm leaving out in that last one. Rainfall is actually a very complex phenomenon, with many components that are still not well understood.)
Time for a Mashup
Now the trouble with simple models is that they usually turn out to be too... well... simple.
For example, I've been talking about random texting and random square dancing is if each was a separate and unique case. As with real people and real texters and real dancers, the physical world is seldom that simple. So, what if for grins we back off a bit from that strict "hands only" rule in random square dancing, and instead permit your dancers to mix in a bit of random texting dances? For example, they might be permitted to send very quick tweets as they are traveling between the hands of other dancers.
What that does is create a sort of spectrum of behaviors that can range between the two extremes of random texting and random square dancing. If only very brief episodes of tweeting are ever permitted, the model looks very much like random square dancing, so you have a liquid. If the need to grasp hands before moving is mostly eliminated, dancers will end up sort of shaking hands sometimes as they pass by, but for the most part they will exhibit the kind of volume-filling behavior seen in the random texting dance. In between those two extremes are the far more interesting and curious situations that come closer to what we see in real liquids and real gases.
The Great Escape
For example, if some degree of texting is allowed, what happens at the boundary between a random square dance and some big open area?
Well, for the most part you will still get the formation of a boundary or surface where everyone is pulled back by the need to hold hands as they move. However, occasionally one of the faster-moving members of the dance will decide to tweet while right at the edge of the surface, and because they are moving fast, they will be out in the open before they can find a new hand to hold onto.
They have escaped! Even though the crowd remains a fluid, allowing short tweets enables some members of the crowd to free themselves and behave like a gas.
That's more commonly known as evaporation. For molecules, as for people, it's an event that is more likely to happen to those who are moving faster and so are able to get farther aware before bonds can pull them back. Notice also that the average speed of the crowd will slow down if you lose a lot of those faster members in this fashion. That's called evaporative cooling, and you only need to stand in front of a fan after an unexpected rain shower catches you outside to feel the impact of the molecular version of that great escape.
Righty Tighty, Lefty Loosey
Now it's time to introduce one more complication: What if you add the rule that dancers can only grasp left hands to right hands? Let's call the left hand a "+" and the right hand a "-" for short. (And why not the other way around? Well, while right handed myself, I've noticed over the years that left-handed folks seem to get snubbed an awful lot in language, literature, manufacturing, and various other subtle and not-so-subtle ways. So, I just think they deserve a "+" for "left" for a change.)
In electrical devices the assignment of $+$ and $-$ is called the polarity of the device, so it’s not too much of a stretch to call dancers with specific roles for their $+$ left and $-$ right hands polar dancers... at least as long as you realize it has nothing to do with how cold it is outside!
I should mention in advance that these random polar dancers have a lot of features in common with water, the most common of all solvents. That is why I’m bothering with these odd complications. Water molecules are close to being ideal molecular polar dancers, in fact, since they are hard to break and have a quite strong difference in real electric charge between the two hydrogen atoms ($+$) and the oxygen atom ($-$). The fact that they have two hydrogen atoms -- roughly the equivalent of having an extra left arm -- also allows water molecules to "network" better with each other as they dance. You might stare at a three-handed dance partner a bit, but those extra hands make for a tighter overall dance!
Red States and Blue States?
With this new and more detailed model of a solvent, it's time to go back to my original example of "dissolving" both Elephants and Dragons into a randomly moving crowd of people.
Originally, I dissolved the Elephants and Dragons into what amounted to a simple non-polar gas, as represented by a random texting crowd. So what happens if you try to dissolve the same Elephants and Dragons into a crowd of random polar dancers with their more complicated mixing rules?
First it’s important to clarify two points. The first is that Elephants have no hands. The second point is that since the Dragons are actually a bunch of humans holding up a costume, they have lots and lots of hands. We're going to assume that their particular dragon costumes allows them to make full use of those hands, and that their hands follow the same $+$ left and $-$ rules as the polar dancers. So what happens in both cases?
The first sharp difference is that the elephants are now actively repelled by the crowd! Since Elephants have no hands with which to bond to members of the random polar dance, the dance crowd reacts to them just as they would an open space: They form a surface at which they hold hands with each other, but not with the elephant... which has none. The result is that the polar dancers end up pushing back against the Elephants and trying to keep them out of the dance. (Some advice if you should ever find yourself in this situation in real life: Do not push on the elephant.)
The situation I just described is remarkably similar to what happens if you drop oil into water. An oil molecule has no "polar hands," which for areal molecule means no molecular-scale excesses of $+$ and $-$ electrical charge on different parts of its surface. That in turn means it doesn't have any easy handles for the dancing water molecules to grab hold of. The highly polar water molecules thus end up joining hands with each other and resisting the intrusion of the "elephantine" oil molecules. It's not that you can't force an elephant into the crowd -- or an oil molecule into water. It's just that the oil molecule will never be accepted very well, and so will always be subjected to forces of molecular-scale surface tension that will try constantly to push it back out to other oil molecules or any nearby surface.
Peas and Carrots
So, what about the other case of the Dragon? What happens to Dragons in random polar dances?
Just the opposite of the Elephant! A Dragon is welcomed into the dance easily, since its many human hand beneath the costume make it resemble an expanded, chain-like version of a water molecule.
You can see this effect whenever you dissolve sugar in water. Ironically, sugar is internally similar to oil, since both typically have large chains of carbon atoms for backbones. However, in the case of sugar, each carbon is "decorated" with the two parts of a water molecule. One part is a hydrogen atom, and the other is an oxygen-hydrogen piece (called a hydroxyl radical). This similarity to water is why sugar is called a "carbo" (carbon backbone) "hydrate" (decorated with water, as in "fully hydrated").
Annie Get Your Cat
All of this is fine, but what about salt? Wasn't the original question about salt, not oil or sugar? Yes, and that require a couple new characters to hand over to the random polar dance. What is needed is this: One-handed robots!
Each of these one-handed robots has only $+$ left hand or $-$ right hand. Since they are manufactured by a small company called Ion Technologies, we'll just call these robots "ions" for short. The company has a sense of humor, incidentally, so it puts pictures of the company cat (named Cat) on its $+$ left-handed robots, and pictures of their founder, Annie, on its $-$ right-handed robots. That resulted in the lefties being called "Cat Ions" (or "cations" for short), and the righties being called “Annie Ions” (or “anions” for short). So, if I happen to say cation I just mean a $+$ or left-handed robot, and if I say anion I just mean a $-$ or right-handed robot.
Breaking Up is Hard To Do... Sometimes
So, if a random polar dance crowd bumps into a squadron of equal numbers of cations and anions, what will happen? Will they be permitted to join the dance, as the Dragon was?
Sure! At least in most cases, that is.
The first problem is that if you have lot of cations and anions together, they will unavoidably lock hands with each other, and likely tightly. However, since the polar dancers have strong polarity themselves and are moving bout pretty quickly, they can easily have enough pull and energy break up even quite tight grips between the cations and anions. Once that happens, the cations and anions can be pulled in to the same wild dance as the polar dancers, and in general, a great time will be had by all.
This situation is of course the one that is analogous to salt dissolving into water. And not just the kind of salt we put on tables, but "salt" in the broader meaning of any compound composed of small, positively charged (usually metal) and negatively charged components, or ions. One of the reasons why water is such a great solvent is that its highly polar molecules can break up nearly any kind of salt or ionic solid into individual ions that then can joint into their dance.
And finally, at last, it's time to return to the original question: Why is it that when a solution of salt (or other substances) in water (or other solvents) is cooled down enough, the salt begins to separate out? And why does the water form crystals that, if he cooling is done slowly enough, contain little or no salt? Or more informally, why does the formerly close friendship between water and salt also seem to cool down dramatically as the temperature drops?
The answer boils down to this: The random dancers aren't always random. That is, if they start moving ever more slowly and ever more cautiously -- the crowd equivalent of dropping the temperature -- you will sooner or later reach a point when a good handshake dominates over a good dance, and the dancers no longer have enough energy to break that handshake.
The reason that happens is that when random motion departs, geometry takes over as king. In this case, geometry dictates that at cold enough temperatures, repetition and monotony will always win out over randomness and diversity. Cold likes to simplify things.
To explain why this is it's necessary to explain why crystals form in the first place. In the case of the two-handed polar dancers the easiest form of crystal to make is as long chain. However, since chains aren't very good at pushing and the goal here is to show how crystals can push things around, I’ll make one more addition to the rules of the polar dancers.
The rule is this: The dancers all have big sheets of Velcro on their backs. So, when things start getting slow and chilly, the first thing that happens to the dancers is they start getting stuck to each other in back-to- back pairs. The results is pairs of dancers with alternating $+$ and $-$ hands sticking out like the four direction on a map. I should emphasize that this is not what happens with water, although you could construct compounds that behave like this. My goal here is just to give a version of the polar dancers that likes to take up a lot of dance floor space when they get together.
So the first step is the formation of these four-handed dance pairs. Then, as temperatures drop still further and the stuck-together dancers grow even more lethargic, the pairs begin to lock hands with nearby pairs for longer and longer periods of time. The situation finally reaches a point where if one pair grasps the hand of another pair, the bond is likely to last for a very long time indeed. That is just what happens to molecules in many of the more remote parts of our world (or universe) in which cold dominates and is unlikely to reverse anytime soon.
Now if you imagine these four-handed pairs linking up with each other, it’s important to notice that because they are formed from dancers who are all the same size, the distances between their remaining hands becomes both exact and repetitious. For example, if you had two long east-west chains of these dancer pairs, then all of their north-facing and south-facing hands will be exactly lined up and perfectly spaced to enable strong grips. That’s very different from what happens if the spacings are variable or random, since in that case it becomes anyone’s guess whether a pair of hands across two parallel chains will match up or not.
This means that repetition due to identical geometry has a dramatically more powerful at low temperatures than you might expect. Random space chains would for example bond only very weakly, if at all. In sharp contrast, repetition of identical units multiplies the overall strength of the bond between the two chains, so that every unit adds yet another "reason" for the chains to bond together. This multiplication means that similar geometry thus begins to emerge a dominant effect when temperatures are no longer high enough to keep pieces moving around randomly.
Now with that point about the power of repetition in mind, what happens if objects like Dragons or Ions that have the right bonds, but not the right shapes or distances between their bonds?
Simple: The non-standard units start getting pushed out. That is, when stronger bonding through repetition begins to take over as temperatures drop, segregation by type starts to become a universal rule for how to achieve the best possible bonding. That's why if you do it carefully enough and slowly enough, it's possible to crystallize very nearly any kind of uniform molecule in existence, even huge, cumbersome proteins. (X-ray diffraction crystallographers often spend far more of their time making such difficult crystals than they do making X-rays of them once they have them!)
All Fall Down
Now if you think about it a bit, the rule of repetition helps explain both why water molecules tend to exclude other molecules, and why salt crystals start to form even before the ice crystals form.
In both cases, better overall bonding through long-range repetition of identical units starts too look more attractive than the weakening power of the random dance. The salt cations and anions, for example, start to get bored with the ever-slower pace of the polar dance, and no longer find its gentle movements strong enough to keep them away from the stronger attraction of their own direct handshakes. As they brush by an existing crystal of cations and anions, the attraction of that crystal now overcomes the weaker bumps and motions of the polar dance, and they decide to drop out. The crystal grows even before the ice begins. Some crystals may add a bit of diversity by combining different types of molecules into a single crystal, but even then there will be repetition in the way the different molecules alternate and repeat within the crystal.
And soon, as cooling proceeds even further, the dancers themselves grow weary and ready to rest. Repetition again rules, and like the anions and cations the polar dancers begin to look for the boring but powerful patterns of repetition that allow them to bond firmly and strongly to those around them. The final crystals form, and the period of rest begins. That rest may range from very short to very long indeed.
And to End, Something Really Cool
But I can’t end a piece like this on such a note! While the universe as a whole tends either towards very hot and random (e.g., the center of a star) or very cold and regular (e.g., the cold clouds of interstellar space), there are a very small number of places where a molecule can wind up cycling rapidly between such extremes, experiences both random dances and the simplicity of cold over again and again. One example of such a very special and remarkable region of the universes is something we call "the surface of Earth." There in this unique environment, a molecule can experience in rapid succession the freezing of water or the flowing of liquids. Molecules of flowing water may themselves enter into the exalted dance of being dissolved into the air, allowing it to flowing to great heights and touch space itself before coming back again in cooler and more orderly forms as water or ice.
And a very few of these molecules will sometimes find themselves entering into systems where the both the randomness of the heat dance and the cold reign of regularity seem to have been turned topsy-turvy. For those few molecules the usual rules of simplicity are somehow replaced by sharply defined complexity and the creation of new molecules that are magnificent both in scale and in the specificity of their functions. The random dance goes here too, but in ways that are controlled and customized towards startlingly specific and incredibly unlikely outcomes. It is the dream vacation for any molecule, the chance to be a part of a world that seems to defy all odds. That destination is of course you, and me, and every other living organism around us. Life is the ultimate gem in the setting of the entire universe.