You can search by producttype parameters, but not by attributes. I've looked carefully in the script that centralizes the searching administrator/com_virtuemart/html/shop_browse_queries.php, and it does not have any provisions for searching by attribute.
If you want to search by an attribute, you must create a producttype parameter, and repeat the attribute value there. I know that this represents double entry work, but I don't see any solution for searching by attribute without modifying the shop_browse_queries.php file.