The biggest problem with natural or vegetarian/vegan friendly dyes is that it is harder to get the really deep deep shades. Ive found that the best dye to do the job (so to speak) is wiltons cake dye. It has a huge variety of colors, though ive only worked with the 12 that comes in their normal pack (each container is something liek 1/2 ounce and lasts a really long time. you can find it in the cake decorating isle of most craft stores). Adding a dash of vinegar will set most dyes (and all food dyes ive ever worked with). Other food syes include easter egg dyes, food coloring, and koolaid.
The most important thing to remeber when dyeing is to go slow- the amount of dye you use and the temperature both play a huge roll in how some dyes will come out, so its important to test the dye before you dye a huge batch. And remember, its easier to start lighter and keep redying than to dye it too dark at first.
Red is probably one of the hardest shades to get in a deep color in food freindly dyes. Even with wiltons it often will have a pink tinge, and since the black has a bit of a prurple tone to it, its hard to get a true scarlet.
My dyes are not toally natural to my knoweldge, since its the synthetic part of it that makes it vegan and more environmental. Most dyes and mordants are very hard on the environment because they use heavy (sometimes metal) bases to bind the dyes to the fiber and use lots and lots of chemicals.
Additionally, many dyes (including natural ones!) are made from parts of animals- especially the color red, which i beleive often comes from the outer shell of a beetle. So that means the the vegan yarn you think you are buying might not be quite so vegan as you think O.o.
theres a bunch of ways to dye yarn that a simple google search will bring up, and knitty.com has a pretty good overview of how to dye with koolaid that can be applied to any food coloring. My favortie way to dye though is to use a crockpot (i have one circa 1970, its teeny tiny, but does the job) since i can let it sit for a couplr hours, the colors blend nicely, and it wont boil like if you leave your fibers on the stove (which will felt them). Crockpots also allow you a bit of leeway in differnt dye methods- you can get an all over even tone, rainbow dye, randomly mix it all up,, etc.