Labels vs Icons vs Both »

From Edward Sanchez »

The debate of icon /  text and icon + text label always fascinated me. Gmail started out with an all text interface and very few icons, recently it changed to the polar opposite and went on mostly icons with very few labels. But which is better? And why?