I am a henna artist, and I incorporate EOs into my paste for smell and for consistency and for terpineols that are in some EOs. In searching for EOs, be sure that it does not say "perfume oil", "aromatherapy oil", or any type of "blend". As far as quality goes, it really depends on what you're using them for. If you're just going for the aromatherapy benes, follow your nose! But if you're using them for something topical, get the best quality. For use internally, I would definitely seek out the advice of a naturopath/herbalist before using anything. Some EOs are quite poisonous, and some of them sound and/or are spelled a lot like something harmless.
Where I get my oils:
Tea Tree oil -- believe it or not, I get it at the evil Wal-mart. (Yeah, I know). It is a very good quality that they have in their first-aid section, near the glycerin (which I NEVER buy there). It is also about 1/4 to 1/8 the prices I've found anywhere else, which is good, because I use up to an ounce for a day's worth of henna paste.
All others -- either at Fresh Fields (aka Whole Foods, aka Wild Oats) or through my henna supplier. Fresh Fields isn't the best place to shop, but they do have a really decent selection of Aura Cacia and a couple others, and they're right down the street. The rarer ones that I sometimes need, I get direct from my henna supplier, Maison Kenzi