The default search functionality in Magento doesn't seem to offer the 'AND' operator when searching by multiple categories. Hence drilling down a search result by one category and then another doesn't give the desired results. I've figured this is something at the core of the Magento and not an configurable option but don't know where to look to try and alter the operator for this.
A rewrite of the following class is needed:
$likeCond = '(' . join(' OR ', $like) . ')';
$likeCond = '(' . join(' AND ', $like) . ')';
There is a free extension called Activo_CatalogSearch which implements this rewrite, but it comes with additional advertising. Take a look how they did it (it's a proper rewrite, no core hack and no copy in
app/code/local), but you could as well do this by yourself.