This is a well-known phenomenon, and a proper explanation is needed. It seems counter-intuitive since common materials expand upon heating due to faster oscillation of atoms. There would be some reasoning to this observation with rubber that goes in opposite direction.
Here is Feynman's intuitive explanation: rubber contains very long molecules like chains. nearby atoms continuously hit this chains. of course you can imagine the stronger hitting be, the shorter will be chain. now heating rubber makes atoms faster, make them hit stronger which makes chains and so rubber shorter.
Late to the party, but I wanted to add my two cents in case someone wants it phrased differently:
Since rubber is made of polymer chains, when the rubber is heated up the long chains twist around like shoe laces or noodles, ultimately entangling themselves and "condensing" the rubber.
When the rubber is cooled down, the long chains "stiffen" and turn into something resembling uncooked noodles, ultimately allowing them to slide away from their neighbors and elongate the rubber.
Think of the type of chain you use on a bicycle, but laid out in a line. In a chain like this, each joint can bend easily but the links cannot stretch easily. Long chain polymer molecules are like this.
When you heat the molecules they jiggle about. All the parts of the molecule jiggle randomly, but they are linked together in this chain. So you should be able to see that when this jiggling occurs, the distance between the ends of the chain must get smaller, compared to the straight chain. And as the chain gets jiggled into more contorted shapes, the distance between the ends must on average be smaller still.
This is happening to all the molecules, and that's the reason why rubber contracts when heated.