I have been using WordPress for several years, but have yet to see a reason to employ tags over categories or tags with categories.
What is the thinking behind the two, and when are each appropriate?
Aside from the technical aspects, Categories are for broad topics while Tags are for adding more detail to your posts' subject.
Lorelle has written the definitive guide on the difference between categories and tags.
You might also want to check out the WordPress.com guide on Categories vs. Tags.
Tags are not hierarchical in WordPress, categories are. That’s the only difference.
Sometimes people make up additional differences but I’ve never seen an argument which could stand a semantic analysis.
For your visitors it is not predictable where you have put your taxons. A good reason to avoid similar taxonomies and use just one.
Way back when WordPress first added tag support, I wrote an article about tags and categories. It's really up to you and how you use them. As @toscho said, by default, Categories are able to support hierarchy, while Tags are a flat namespace. Also, you can create custom taxonomies, which can also optionally be hierarchical. And in fact, Categories and Tags in WordPress are just specific, default implementations of taxonomies.
A popular example for using multiple custom taxonomies is for a realty site. You might define several different taxonomies, each of which can let you select properties by different qualities: neighborhood, price range, number of bedrooms, etc. By cross-referencing multiple taxonomies in this way, it is possible to narrow down selections fo content very nicely.
Anyhow, the most common usage for Categories is to organize posts into broad, non-overlapping topics. Tags are used to supply additional keywords related to the content, but which might not appear in the content itself. For example, if I write a post about a game on my iPhone, I might not ever specifically mention the iPad. But I might want to add an 'iPad' tag, because the game is also available on that platform, and I want others to know that.
As is stated in most of the answers here: Categories have a hierarchical structure while Tags do not.
I would add to the above that it helps to only have one category assigned to a post, but as many tags as you want. This helps me keep organised.