Much like the FO/EO thread, I thought this could be a place to compile information for beginners and advanced soapmakers alike on coloring your soap. PLEASE add any feedback or knowledge you have!! The information below is compiled from a few years of soaping, a few trusted sources and lots of trial and error!
First and foremost, things with which you should NOT dye your soaps:RIT cloth dyeFood coloringPaint, of ANY kind (powder or liquid (while paint no longer contains lead, it does contain other metals and chemicals that are NOT safe for skin! Nor would they work with the saponification process!)
Candle dye (unless the specific brand you have bought says otherwise)
Potters' glaze or ceramic paintDISCLAIMER: As always, check with the supplier/manufacturer of any product should you have questions. This is meant to be a general "rule-of-thumb" guide provided by myself and other Craftsters. 
Natural Colorants: Natural colorants are exactly that: natural, or non-synthetic. The plus side of natural colorants is that they are natural (for those who like to bear the "all natural" label) and some colorants can have excellent benefits for your skin. The cons of natural colorants is that some can be irritating to the skin (see list) and some can be costly to use because the amount needed to make a decent color is staggering.
Alkanet Root/Powder: A popular dying agent with all kinds of applications, alkanet can be used to create colors anywhere from grey, purple, pink or blue depending on the oils used (it is sensitive to the alkaline levels). MamaVSoap says: "Steep the herb in olive oil and then use it in place of equal amounts of base oils (4 ounces colors a 6# batch nicely)."
Annatto Seed: A plant from Central America, Annatto seed produces lovely yellow and orange shades.
Cinnamon: Cinnamon is one of the colorants you need a LOT of to get a decent color. The problem is that it can then make your soap VERY scratchy. I use cinnamon as an accent piece rather than colorant to give soaps a warm, spicy look.
Cocoa: Regular ol' Hershey's baking cocoa can be used to achieve lovely, rich brown colors. It doesn't make the soap scratchy, and adds a nice cocoa smell. I recommend using it with scents that compliment cocoa! As an FYI, some people who are allergic to chocolate can possibly be allergic to cocoa in soap.
Comfrey Root/Leaf: A plant known for its healing abilities, it creates a lovely sage green color. It should be noted that if you are using comfrey root in, say, a hand salve, lotion or soap, you should plan for that product to be GREEN and not waste colorants trying to die it pink!!
French Green Clay: Talk about luxurious! French green clay has loads of skin benefits (because it draws oil from the skin, it's often found in facial products) and creates a lovely, muted green color.
Henna: When purchasing henna, make sure you have PURE henna and not some of the other products that add other ingredients. Henna works well as a colorant and generally achieves a brownish-red color (think Burnt Umber crayon). I have heard stories of soapers using a little too much henna and dying their skin when they used the soap, but I don't know if that's soap-urban-legend or not!
Kaolin Pink Clay: A wonderful clay for sensitive skin, From Nature With Love's website sums it up best: "Pink Kaolin Clay is a gentle clay, making it suitable for sensitive skin. It helps stimulate circulation to the skin while gently exfoliating and cleansing it. Pink Kaolin Clay does not draw oils from the skin and can therefore be used on dry skin types." It does create a lovely pink shade.
Paprika: Much like cinnamon, a little of paprika goes a long way. It's best to use a smidge and achieve a peachy-red tint as too much (i.e. if you're trying to achieve the actual color of paprika) will make your soap VERY abrasive.
Saffron: While saffron can certainly make a lovely colored soap (I've seen some at craft fairs) it is a VERY pricey herb, and the amount you would need to get a rich color would make the price exorbitant.
Artificial Colorants:Artificial colorants are man-made and synthetic. Buy them from soap suppliers and make sure they are approved for skin contact! Also, be sure to check if a given dye is suitable for your chosen application. Some dyes are okay for MP but not okay for CP, while others are not okay for lip balm. So read your fine print! Artificial colorants are FDA approved and while many "granola" folks (I'm sending evil thoughts to a gal from Boulder right here...) will argue that that doesn't mean they are safe... there is no evidence to suggest they are not. The pros of artificial colorants are that they are often affordable, they create rich, vibrant colors you cannot achieve with natural colorants and you can get any color under the rainbow!
Artificial colorants come in the following categories:
Ultramarines (powdered):No, not the army from Warhammer 40,000.
Ultramarines are now entirely synthetic (they were originally derived from lapis lazuli) and typically come in shades of blue, pink & purple. A little of these go a long way which means you typically get more bang for your buck. Most purple and violet ultramarines tend to look grey when your soap is curing. Often times this grey period passes.
Oxides (powdered):Oxides DO get their name from iron oxide and most oxides do contain iron in them. Reds, especially. They come in shades of red, yellow, green, black & white. While a little green goes a long way, I find that more of the others are needed to achieve rich colors. I have made black soap before, and it took a TON of black oxide to achieve! Some people claim that titanium oxide (white) cuts down on lather and moisturizing but honestly I've never noticed, but I may just not use enough of it. Typically white is used to lighten shades and black is used to darken.
Liquid Dyes:I'll further break this category into 4 sections:
1) The garbage you buy at Micheal's, Joann's, Hobby Lobby, etc: Don't bother. Much like the fragrances they are weak and do NOT produce good colors. Their idea of "red" is my idea of plum purple...
2) Melt & Pour, Lotion, Salve, etc. Dyes: These colors generally say "not suitable for CP" but work well in other applications. I'm told often times it's the heat of CP that mutates these dyes, and other times that they don't react well with lye. I prefer liquid for MP, scrubs, shampoo, lotions, etc. because they disperse easier. Using powdered oxides in MP is an exercise in frustration sometimes!
3) CP Dyes: There are a few liquid dyes on the market suitable for CP soap. Often times they are merely oxides or ultramarines that have been reconstituted with a carrier oil. I've used the LabColor line from BB and while I was pleased with the results, I didn't like it as much as the powdered variety.
4)Lip balm safe colorants: These are generally liquid (some, like Micas can be powdered) and are safe to use on your lips. Majestic Mountain Sage sells them in a "hobbyist variety pack" and because such a little goes a long way, that HVP has lasted me a good long while.
Micas:These generally have a lovely sheen and sparkle to them. My experience in CP with mica has not been favorable. I find that the amount needed to achieve any sort of color is ridiculous and because CP soap is not (typically) transparent, the sheen and sparkle are lost. However in MP & lip balms these colors are fun!
I'm sure there is a TON I've forgotten, but it's late and I can always come back and edit.
