How do I override the search template in a plugin?

You can use template_include filter hook

add_filter('template_include','my_custom_search_template');

function my_custom_search_template($template){
    global $wp_query;
    if (!$wp_query->is_search)
        return $template;
    
    return dirname( __FILE__ ) . '/my_search_template.php';

} /*UPDATE: there was a missing ";" after $template*/