Not sure if this has been covered before, but I just discovered that you can add color labels to messages in Mail.app (like you can in the Finder). Just select the message(s) you wish to color, then select 'Show colors' from the 'Format' menu. Click on any color and voila -- the selected message(s) in Mail is now highlighted that color.
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...]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20040621002608797