Firstly, don't get too sidetracked by the exothermic Heat of Solution. While it is true that many of these salts "react" with water when they dissolve and release heat, that has little to do with their "ice melting" ability. "Ice melting" in this context usually refers not to the original melting of solid ice, but rather to the fact that the salt/water mix produced stays liquid rather than crystallizing back to ice.
The key is the colligative property, as mentioned by others, that ANY solution of a solute in a solvent will have a freezing point LOWER than that of the pure solvent. How much lower depends on which solute, and on how much is present. And the "how much" part must be measured in MOLARITY - that is, how many MOLES of the solute are dissolved per liter of solution. In reference books you can find tables of the Molar Freezing Point Depression Constants for many solutes in water.
Now, at any temperature below the freezing point, there is a dynamic equilibrium between solid water (ice) and a bit of liquid water. When you sprinkle a salt on the ice, it immediately starts to dissolve in the water phase, and the resulting solution now has a much lower freezing point, so it will not re-crystallize unless the temperature is reduced. This disturbs the equilibrium, so now more of the solid phase melts to liquid, and this keeps up until the liquid phase becomes more diluted to the point that its melting point is close to the ambient temperature. Note, however, that if it really is cold enough outside, even this salted liquid phase will have a freezing point higher than the really cold outside, and it will freeze anyway. In other words, salt still will not melt the ice and keep it slushy if the temperature is too cold.
I trained in Physical Chemistry, but I cannot remember clearly the molecular-level explanation of these colligative properties. It is very tempting to talk about the presence of ions in the water interfering with the normal hydrogen bonding between water molecules, thus reducing their ability to align into a rigid crystalline structure. (And yes, I did use the term "hydrogen bonding". This is neither ionic nor pure covalent bonding, but a form of weak covalent bonding involving hydrogen atoms almost shared between molecules.) The problem with that explanation is: how does this account for boiling point elevation? If the ions' presence interferes with attractions between water molecules, should that not make it EASIER to convert liquid water into gas? That is, one might predict that the Boiling Point would get lower, but in fact it goes higher when you dissolve a salt in water!