Programatically Changing the "Nothing Found" Query Text

I am writing a query plugin and need to add to the “Nothing Found” page if the query is unsuccessful. For example, user types in query [musical instruments] and the Nothing Found page shows up: I’d like my plugin to add to the page and explain adding OR between the queried words will return documents that have one of the two words. I’d also like to add other query tips.

Of course I know the template can be edited, but I need to do this from the plugin regardless of the template used. Of course in the admin I will provide a way to turn off the “query help” info from being added to the nothing found results page.

So…how do I make this happen from the plugin side of WP?