It's a bit inaccurate to say that salt melts ice, although that is definitely how things appear at temperatures near the normal freezing point. It's more accurate to say that salt lowers the freezing point of water, and it does this by dissolving. It isn't just salt that can do this; any substance that dissolves in water lowers the freezing point. That includes rock salt. However, because rock salt granules are larger than table salt granules and contain more insoluble impurities, they don't dissolve as well and don't lower the freezing point as much.
TL;DR (Too Long; Didn't Read)
Rock salt and table salt both lower the freezing point of water by dissolving in it. Because rock salt particles are larger and contain impurities, though, the rock salt particles don't lower the freezing point as much as table salt.
Substances That Dissolve in Water
The water molecule is polar. When a pair of hydrogen atoms bond with an oxygen atom to form H2O, they arrange themselves asymmetrically, like proverbial Mickey Mouse ears. This gives the molecule a net positive charge on one side and a negative charge on the other. In other words, each water molecule is like a tiny magnet.
For a substance to dissolve in water, it must also be a polar molecule, or it must be capable of breaking into polar molecules. The large organic molecules that make up motor oil and gasoline are examples of non-polar molecules that won't dissolve. When polar molecules enter water, they attract water molecules, which surround them and carry them off into solution.
Salt dissolves so well because it completely dissociates into positive and negative ions in water. The more salt you introduce into solution, the higher the concentration of ions becomes until no water molecules are left to surround them. At that point, the solution is saturated, and no more salt can dissolve.
How Salt Affects Freezing Point
When water freezes, water molecules don't have enough energy to remain in the liquid state, and the electrostatic attraction between them forces them into a solid structure. Looked at another way, when water melts, the molecules gain enough energy to escape the forces binding them into a solid structure. At the normal freezing point (32 F or 0 C), there is an equilibrium between these two processes. The number of molecules entering the solid state is the same as the number entering the liquid state.
Solutes such as salt occupy space between the molecules and work electrostatically to keep them apart, which allows the water molecules to stay in the liquid state for a longer time. This upsets the equilibrium at the normal freezing point. There are more molecules melting than there are molecules that are freezing, so the water melts. However, if you lower the temperature, the water will freeze again. The presence of salt causes the freezing temperature to decrease, and it continues to decrease with salt concentration until the solution is saturated.
Rock Salt Doesn't Work as Well as Table Salt
Both rock salt and table salt have the same chemical formula, NaCl, and both dissolve in water. The main difference between them is that rock salt granules are larger, so they don't dissolve as fast. When water molecules surround a large granule, they gradually strip ions from the surface, and those ions have to drift off into solution before the water molecules can contact ions deeper inside the granule. This process can happen so slowly that the water may freeze before all the salt has dissolved.
Another problem with rock salt is that it is unrefined and may contain insoluble impurities. These impurities may drift off into solution, but they won't be surrounded by water molecules and don't affect the attraction the water molecules have for each other. Depending on the concentration of these impurities, there is less salt available per unit weight as there is in refined table salt.