How do I let users exclude/include specific categories, so that
everything (archives, search, etc) is limited to those categories?
I’ve seen admin-side plugins that let me limit what others see, but
not ones that let users choose what categories to see.
Ideally, this would even work for unregistered users.
Use the plugin Taxonomy Drill-Down from @scribu.
The My Category Excluder plugin allows users to specify which categories they want excluded, it also allows the blog admin to specify which categories users can choose to exclude.
It doesn’t provide this functionality for non-registered users, so you will have to modify it to suit your needs.