Taxonomies are categorized directories of information. A directory differs from the index used by a search engine because a directory uses a structured way to categorize sites. An often-used analogy is that a directory is like the table of contents in a book, while the search engine index is like the, well, index to the book. In other words, the directory tells you how the book is organized, while the index allows you to search within the book for specific keywords.
It's a not-so-well-kept secret that one of the best approaches for getting good placements in the search engine listings is to enter through a back door, by working with the two most important structured directories: the Open Directory Project (ODP) and the Yahoo! Directory.