The Google Blog announced that Gmail has added colors to labels.
Labels in Gmail are basically virtual folders. Assigning labels by actions can really streamline how you use email. Google has decided to add colors to labels in order to make the labels you defined more visual. If you want to add colors to your labels, follow these instructions. For more help on labels, go here.
Note: This new feature is only available in IE7 and Firefox 2 browsers.
More coverage can be found at Techmeme.