Natively, Virtuemart provides pretty boring language for search queries that return no results.  When you search for something using the Virtuemart Search Module that doesn't have any results, the system spits out the following result: 

Your search returned 0 results

This works ok if your customers are browsing for blog articles or general pages but this really doesn't help you close any sales or at least guide your customers to get the information they need.

So changing it is easy.  Believe it or not, the seach module's php file has NOTHING on how this is done.  The search results are actually part of the browse system of Virtuemart.  As such the language is part of Virtuemart, not your search module.  

The language can be found at: administrator/components/com_virtuemart/languages/common/english.php

At or around line 57: 'PHPSHOP_NO_SEARCH_RESULT' => 'Your search returned 0 results',  

Change everything within the ' ' after the => to whatever you like and your all set!