Matt at WordPress.com explains the difference between categories and tags:
What’s the difference between categories and tags, you ask?
As best as I can explain it, categories are things you create ahead of time and only have a few of. Imagine them like sections of your site. The signs on aisles of grocery stores. Tags are one-off keywords attached to a post. You may add a tag to a post that you’ll never use ever again. Categories are meant to be permanent, tags are ephemeral.
Since WordPress version 2.3, tagging has been a part of the core system. Until then tagging was only available via a plugin. Matt's post is about WordPress.com hosted blogs but his answer should help you understand a little better how to use categories and the advantages of tagging for your WordPress powered site.
See also: WordPress 2.3 Tag News