After enabling Superstars in Gmail Labs and clicking on "Save changes", go to the settings and select the icons you want to use. The exclamation mark is useful to flag important messages, quotes could show that a message needs a reply, while the info icon could be used for messages that contain valuable information.
To star messages faster, enable keyboard shortcuts in the settings. "The superstars will rotate when you press the 's' keyboard shortcut or when you click successively," explains Google. "Rotating through the superstars only works when you click (or hit 's') successively. If you pause for a second, then the next click will turn off the superstar. It's designed this way so that if you never click successively, then you'll just get the original on/off toggle behavior."
If you want to find the messages that have a certain kind of star, use one of the following queries:
has:yellow-star (or l:^ss_sy)
has:blue-star (or l:^ss_sb)
has:red-star (or l:^ss_sr)
has:orange-star (or l:^ss_so)
has:green-star (or l:^ss_sg)
has:purple-star (or l:^ss_sp)
has:red-bang (or l:^ss_cr)
has:yellow-bang (or l:^ss_cy)
has:blue-info (or l:^ss_cb)
has:orange-guillemet (or l:^ss_co)
has:green-check (or l:^ss_cg)
has:purple-question (or l:^ss_cp)
You can enable the Quick Links labs feature to save some of these queries so that they are always accessible with a single click. Just search for has:blue-star or any other value and click on "Add Quick Link".