Warning: Long post ahead!
I’m going to second Lilairen and recommend the Lush henna, which they call “Les Cacas”. I’ve only used it once, but I really liked it. I’ll tell you about my lone experience.
Okay, I’m going to sound a bit like an advertisement now, but I love almost everything Lush and I recommend them very highly. (I’m a member of their forums, too!)
Their henna, unlike any other henna I’ve ever seen, is a big bar of henna and other ingredients and butters. Admittedly I’m not an expert but all other henna I’ve seen was in a powder form. Lush’s has an extra step because of this - it needs to be soaked in hot water to make it into a paste. Alternately, you can grate it with a grater - this is the recommended way.
Lush henna comes in four colours: Caca Noir (blue-black-dark brown), Caca Brun (brown), Caca Marron (kind of a reddish chestnut colour) and Caca Rouge (bright, bright red).
For my hair, about shoulder-length at the time, I used half of a bar of Lush Caca Noir. I’m a bit adventurous with my hair and wouldn’t be alarmed if I had to cut it off, so even though you’re not supposed to henna over dyed hair, I did it anyway. I’m one of those “It’s just hair, it’s on my head for me to play with!” people. Anyway, it worked, though it had a slight green tinge due to reacting with the metallic dye on my head for maybe a week. Otherwise and afterwards, it was a deep blue-black-brown. I know that doesn’t sound like a possible colour, but it is. Wish I had a pic, but I don’t have a picture of me with my plain hennaed (?) hair, just one after I decided to bleach streaks into it and dye them blue.
I didn’t add any special ingredients - just followed the package directions. (At the store where I bought it, they handed me an instruction sheet, but as Lilairen said, Lush has the instructions online.) I grated it, added the hot water and let it sit in a bowl which was resting in a pot of hot water. You have to let it sit and keep it heated, because that brings out the colour. Apparently, the longer it sits, the more dye it releases. Some people put it in an oven-safe dish and leave it in a warm oven. Don’t microwave it, though. You don’t want to cook it.
Do not touch henna with any metallic utensils. Use plastic or glass only. Metal and henna react with each other.
I should have added more water. I tried to make it look like cake batter, but it still needed to be a little thinner. As a result, my hair sort of strained out the water which ran down my face, and the henna itself stayed on top of my head. I was constantly wiping dribbles. I left mine out to dry in the open air as that gives Caca Noir its bluish tone… if I had wrapped it, it would have turned out more reddish/brownish. If you’re using one of the reddish colours, wrapping is a good idea. I always use a plastic bag whenever I wrap my hair, but you could also use a cheap showercap as suggested above.
It smelled a lot like grass while it was in, but left a nice scent on my hair afterwards. Kind of a hippy-ish scent, though.
Lush refers to black henna, but “black henna” is really indigo. Indigo over henna gives black hair, so Lush’s Caca Noir bar contains indigo and red henna.
Some links:
http://www.lushcanada.com (I saw your location, hehe. This is where you can see pictures of the bars, and reviews, and even buy it if you feel like making the leap!)
http://forum.lush.com/forum/viewtopic.php?t=19511 (Caca FAQ, and if you have any questions, you can register there and ask!)
http://forum.lush.com/forum/viewtopic.php?t=19438 (Before and after pictures of Lush henna users)
And a couple more things. The others in this thread are posting that their henna wore off? Wow, mine sure as heck did not. I like to change my hair colour frequently. I have now bleached it three times and dyed over it at least six times, and my henna is well over a year old… and it’s STILL there. That’s the reason I will not henna again until I am sure that I’m finished dyeing my hair forever. It just does NOT come out. Again, I know you’re not supposed to try to bleach or dye over henna, but I’m a daredevil. I wouldn’t recommend that anyone else do this, unless you’re a daredevil with your hair too.
Also, again unlike others in this thread, my hair was really shiny and felt very healthy afterwards! If it weren’t so danged permanent, I’d use the rest of my bar one of these days.