This list is culinary herbs only:
Perennial herbs are oregano, sweet marjoram, sage, rosemary, winter savory, salad burnet, thyme (although it can be short-lived and have to be replaced every 3-4 years), garlic chives and onion chives, and bay (laurel nobilis, not the California bay). All of these take sun, although here in the south, they will appreciate a little afternoon shade in the height of summer. This is by no means a complete list--just some of the ones we grow.
Annuals are the basils, parsley (actually biennial, but it gets tough the second season), chervil, cilantro, and fennel.
The mints will grow happily in shade. Just be sure to keep them in a pot because they are extremely invasive. It is also a good idea to keep them as far apart as possible so they don't cross-pollinate and you end up with some funny tasting mints.
The site for your herb bed is ideal--handy to the kitchen when you want to add something special to a dish at the last minute. Don't amend the soil very much, and don't fertilize. Herbs like a little stress and lean soil, otherwise they get big, lush, and tasteless.
If you have more questions, e-mail me and I'll try to help.

To add...

Sorrel will tolerate a wide range of conditions and it's sour lemony taste is pleasant. It can be used fresh as a green (sparingly) or in cooked dishes as seasoning, especially in classic french recipes. I have some in the edge of the only patch of sandy soil on the property that is partial shade due to tree cover. Horseradish, chives, oregano, rhubarb, and egyptian onions (aka walking onions) all are thriving there.

Lovage will tolerate some shade as well. I have one under the edge of a crabapple tree so partial shade. Since it's 8 years old and grows as tall as I am, I don't think it's unhappy at all. Lovage has a mega-celery taste.

FataMorgana