Green:
The best green is chlorophyll, and this is found in any dark green vegetable, and in algae such as chlorella or spirulina.
When adding it to a brew, do not add it too early, as the yeast will absorb the color and it will be a waste. I recommend adding it 6 hours or less prior to bottling.
The green of chlorophyll is destroyed by heating (becomes pheophorbide, which is a browner olive green). Extraction should be made in at least 40% alcohol prior to brewing. This extract should be added at the same time as the yeast (ie, when stuff is cool). Under alkaline conditions, a water soluble bright green compound (chloropyllide) is extracted, but best to forget about getting this complicated unless you have a basic understanding of chemistry. Freezing prior to alcohol extraction might improve the yield.
I have used spirulina for this, although it does add its characteristic odor to the extract. I think chlorella has a more neutral flavor, and it is a true green, while spirulina is a blue-green. I dump some in a small glass jar, add Everclear (95% alcohol), and a few drops of reagent grade KOH (Potassium Hydroxide, 10grams in 50ml water) solution to alkalinize it. I do add a little bit of water also, so that my alcohol content is between 60-80%. If vodka is used, do not add extra water. Let soak at least overnight, and it is ready for use.
However, it is possible that chlorophyllides and pheophorbides contribute to photosensitivity dermatitis, although for most people this should not be a problem.

Red:
Elderberries and hibiscus flowers have anthocyanins that give a wonderful red color when heated in water. Hibiscus flowers also have a natural acidity, and so will also add tartness. This is not a problem if the tartness is desired. If alkalization is desired, a few drops of KOH may be used cautiously (be careful not to overdo things). But beware that over much changing of the pH may adversely affect the color (such as turning it green or violet). Best to keep things on the acidic side for this red.
Beets have betanin, but this compound is unstable in heat or light.
Blueberries and blackberries give a nice deep red, while raspberries give a brighter lighter red.

Violet:
Anthocyanins from red cabbage and purple carrots. This is water soluble.

Orange:
Carotenes from paprika. Carotenes are oil soluble, and not water soluble. It may be possible to make an alcohol extract...but I need to research this further. Orange peel will give an orange color boiled in water.

Yellow:
Beta Carotene from carrots. Possibly tumeric. Carotenes are oil soluble, and not water soluble. It may be possible to make an alcohol extract...but I need to research this further. Anything brewed with honey will be slightly yellow depending on sufficient quantities of honey (2 lbs per gallon).

Brown:
Heating chlorophyll will give an olive brown. Tannins from strong tea, or brown spices (cinnamon, clove, cardamom, etc) will darken things, although one will also get the flavor from thses spices. I have found that using Lipton Spice Chai tea bags does a great job of darkening meads without changing too much of the flavor.

Black:
Now this is a true challenge... I have yet to achieve this... although theoretically, red + green should come close.