Or, to ask this another way - "Why does water expand when it freezes?" For something to float, its density must be less than that of the environment. Helium, having less mass per volume than air, floats. Ice, although it is a solid, is actually less dense than water. Water is one of the few liquids that has this particular property. This is due to the fact that water spontaneously forms ordered crystals when frozen.

First, lets mention an important aspect of the physical nature of water. Water has two hydrogens and one oxygen. Oxygen is a great donor and acceptor for forming hydrogen bonds. Hydrogen bonds are formed by sharing one hydrogen between two oxygens: O...H-O. This bond is strong enough to affect the physical properties of water. In the liquid state, many waters are involved in large transient networks of these hydrogen bonds. This is why water has such a high boiling point relative to heavier liquids. Gasoline is heavier on a per molecule basis, but it doesn't form extensive hydrogen bonds so it is more volatile.

These hydrogen bonds, which give the water strength also have an effect on the structure of ice. The hydrogen bonds between individual waters forms a crystal lattice in the solid state. This crystal is arranged in such a way that there is more space between water molecules than in the liquid state. As a result, the bulk water on a whole, increases in volume. The denisty is less, ergo the ice floats.

This is also why they say that ice skaters are not skating on ice, but a thin layer of water. By squeezing the ice with the skate blade, you are forcing the water molecules closer than they like to be in ice, causing it to melt. Of course, once the skate passes, the water quickly expands and refreezes. I suspect, although I haven't tested this, that water which has been flash-frozen (nearly instantaneously) will not expand as much, because ice hasn't had the chance to form ordered crystals.

This node ignores the second half of the issue which is the origin of buoyancy. Why does something lighter float in something heavier. See the buoancy node for a description of that phenomenon.