I got big into natural dying a few years back... It's really fun to find plants in the back yard, prep them, and use them to color period clothes. Really makes wearing them come alive for me.
The things I took away from it: wool is the easiest to dye with natural dyes, mordants make all the difference. (A mordant is substance that you use to pre- and/or post treat cloth, it both helps set a dye, and affects the end color) A good source for mordants is:
http://earthguild.com/products/dyes/dyemord.htm
Most of my experiments were with Yarrow, which is VERY abundant here, and I think throughout the US in overgrown meadow areas. Depending on the mordant it will produce a grey, green or yellow. Most any plant has some sort of dye use, including most tree species, (around here spruce, birch & willow are good dye plants).
Anyway, if you want to buy premade natural dyes, woad (blue/indigo color) and madder (red) were about the most common dyes in medieval Europe and translate well to Middle Earth, are available at Earthguild which I linked above.
).