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, though expensive.
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 dragonsblood.
Green was a popular color for interior walls of a house apparently, 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 emeralds were the most sought-after gemstone.
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, and it needed lots of alum. "Alum" refers 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.