Alex King compares two techniques for customizing WordPress: Custom Fields and Taxonomies.
Custom fields are still the right choice for misc. data that is used for display purposes only, or descriptive data about a post that is used by a behind-the-scenes process. You can serialize data here to store the equivalent of cached relational data. You can set flags for various behavior triggers, etc. You can also create a custom user interface for adding and editing the data you need to store.
Where you should use a custom taxonomy instead is for any data that you need to query on. For example, getting all posts that were broadcast to Twitter; all posts that were created by an outside process; all posts that have a certain workflow status.
The reason to favor a custom taxonomy in these situations has to do with the WordPress database structure. Queries by taxonomy are well optimized as this is a primary front-end presentation feature in WordPress core. Conversely, querying by custom field key and value is slow. The value column in the custom field table is not indexed – you are basically doing a search through data that is not intended for that purpose.
Bottom line: database queries are faster for taxonomies, slower for custom fields.