Woad was a plant in the mustard family, and ancient burials in Germany and the UK have found evidence of woad being used thousands of years ago. It was not a consistent blue, however, and its result ranged from a grayish-blue to black. It also took several months to produce properly. Indigo was a more reliable blue.
Madder root was used to make red, and gave its name to the color rose madder. A darker red could be unstained by repeated dying, or from an import from India called dragons
blood.
Green was a popular color for interior walls of a house, but for clothing it had different connotations. It could be considered unlucky to wear because it symbolized the decay after death. Chaucer's Yeoman, however, wore green because of its rustic connotation. Bright green clothes were associated with the rich, just as the emerald was the most prized gem.
To produce yellow there was a plant native to Europe and Western Asia, called by many names such as dyer's rocket or weld. When picked before the flowers became too mature, it produced a bright yellow that worked well on linen, silk, and wool.
Black was a difficult color to produce in fabric, but had strong symbolism that made it desirable for different classes. It required a mixture of madder, woad, and weld. It also needed lots of alum. Alum referred to a salt (potassium alum, or sodium alum, or ammonium alum), known to Pliny and earlier as an astringent substance helpful in dyeing (and medicine). Black was considered a "humble" color and used for clerical garb. The complexity which its manufacture required also made it desirable by the upper classes. Along with red and purple, black is most often listed as one of the colors restricted to the elite.
I'll share the sources of more colors tomorrow.