Aurora Silk Natural Dyes
Also sells books on natual dyeing, and silk fiber.
George Weil Fibrecrafts Dyes
British source for many period dyes, including the more hard-to-find persian berries, weld, safflower, elderberries and Dyer's Greenweed.
Prairie Fibers Dyes
A wide variety of period dyes and mordants.
Griffin Dye Works
Many,many period dyestuffs, including materials for very early period dyes: pomegranite rind, lac, myrobalan, red earth. Also carries rare mordants & modifiers: unslaked lime (aka calcium oxide), hartshorn, urea, clubmoss, oxalic acid, & bran.
Hill Creek Fibers
Basic mordants; good selection of period dyes, including woad powder (aka "Bleu de Lectour").
Black Walnut Hull Powder from Kalyx.com.
Kalyx sells this in bulk, enough to dye with. The dyestuff in Black Walnut hulls is very similar to that in english walnuts, a common brown dye of the middle ages. Best results are obtained using a 1/1 ratio of powder to fiber, and soaking the powder for 24 hours beforehand. No mordant is required.
Woad Dye from Bleu de Lectour
Renaissance Dyeing
If you want naturally dyed silks and yarn but don't want to do it yourself, this company specializes in naturally dyed fibers using historic dyestuffs.