It would really be better if you could do this via a contextual menu, like you can in the Finder. Perhaps someone can create an AppleScript to make it a bit quicker.
[robg adds: Amazing; nearly four years of Mail use, and I'd never thought to try this (of course, who knows when it started working...). I know you can create rules to color items based on criteria, but this is a great trick if you just want to color a selection of messages on a one-time basis. It's amazingly fast to do, especially if you have the screen real estate to just leave the color wheel open. Note: I switched the "internationally correct" spelling of 'colour' in this hint to the US standard of 'color,' just to make it easier for those doing searches...]

