Why would a protein need to bind to ice?
Well, ice can be a significant problem for cells, and therefore for the organisms that are made from those cells. Crystals generally have sharp edges that can pierce membranes; they also render immobile the flow of small molecules and proteins in the cell.
The solution to this problem - faced by many creatures that live in cold climates - is to bind any crystals of ice before they have a chance to grow larger. Even if the crystalisation process cannot be stopped completely, the ice particles can be made more rounded and less damaging to the membrane.
How does it bind to ice?
Ice is, of course, just frozen water - and all proteins have some interaction with their solvent. However, the water molecules in ice are arranged in a regular array (a crystal), so that the best way to bind is to have regular spacing of surface residues. In other words, there is a pattern to the groups on the outside of these proteins which mirrors the structure of the ice. This is clearest in those proteins with a solenoid fold or beta-helix, which is a very regular coil structure1. The surface groups that bind the ice are spaced along one (or more) of the coil's surfaces, with the same separation as the distance between turns of the solenoid.
However, a quick search of CATH for the word 'antifreeze' reveals that most entries are class 4 (few, irregular secondary structure) which suggests that not all these proteins rely on the fold to orientate their binding residues. Indeed, there is good reason for not grouping them together as 'antifreeze' proteins - not all of these ice-binding proteins are designed for freeze prevention! At least one creature, a type of toad, encourages freezing of its body while supressing the growth of membrane damaging crystals inside the cell2.
SEE ALSO: antifreeze glycoprotein.
1 See eg : 1eww - Spruce IBP, 1ezg - Budworm IBP.
2 Good article in Nature by Christopher Surridge from 20 July 2000.