I stumbled over this looking myself for a solution to order posts from WP_Query by their related terms, which seems to be the quintessence of this question. (I’ll answer to the special search case of the question below the general description.)

Sorting Posts by related Terms

So the key is the MySQL function FIELD() which allows to solve these problem by attaching only one filter to posts_orderby in combination with the use of tax_query.

Using the tax_query parameter of WP_Query is necessary, to »JOIN« wp_posts table with wp_term_relationships whose column term_taxonomy_id we want to order by.

If it is not wanted to queue for specific terms, just pass all terms as value:

# get all terms of 'category' ordered by the terms name (default behaviour)
$terms = get_terms( 'category', array( 'fields' => 'ids' ) );
$query_args = array(
    'tax_query' => array(
        array(
            'taxonomy' => 'category',
            'field'    => 'id',
            'terms'    => $terms
        )
    )
);

/**
 * the filter callback
 * removes itself from the applied filter
 *
 * @wp-hook posts_orderby
 * @param string $sql (Default oderby clause)
 * @param WP_Query $query
 * @uses $terms which are allready in the correct order
 * @return string
 */
$orderby_terms = function( $sql, $query ) use ( $terms, &$orderby_terms ) {
    $field = $GLOBALS[ 'wpdb' ]->term_relationships . '.term_taxonomy_id';
    $terms = array_map( 'intval', $terms );
    $sql = sprintf(
        'FIELD( %1$s, %2$s ) ',
        $field,
        implode( ', ', $terms )
    );
    remove_filter( current_filter(), $orderby_terms );

    return $sql;
};
add_filter( 'posts_orderby', $orderby_terms, 10, 2 );
$query = new \WP_Query( $query_args );

To answer the question more detailed: as you need the tax_query parameter

Limitations

• This Query won’t fetch posts, which aren’t assigned to any term. That’s relevant for other taxonomies than category.
• In case a post is assigned to many terms, the sorting might not be as comprehensible as you would expect, because for each post only one term-relationship is considered (GROUP By clause in the SQL).

Special Case: Search Queries

The way described above can be applied to the default search query as follows:
You hook into pre_get_posts and make sure it’s the main search query.

function wpse_91993_order_search( $query ) {

    if ( ! $query->is_main_query() && ! $query->is_search() )
        return;

    $terms = get_terms( 'category', array( 'fields' => 'ids' ) );
    $tax_query_args = array(
        array(
            'taxonomy' => 'category',
            'field'    => 'id',
            'terms'    => $terms
        )
    );
    $query->set( 'tax_query', $tax_query_args );

    /**
     * the filte callback
     * removes itself from the applied filter
     *
     * @wp-hook posts_orderby
     * @param string $sql (Default oderby clause)
     * @param WP_Query $query
     * @uses $terms which are allready in the correct order
     * @return string
     */
    $orderby_terms = function( $sql, $query ) use ( $terms, &$orderby_terms ) {
        $field = $GLOBALS[ 'wpdb' ]->term_relationships . '.term_taxonomy_id';
        $terms = array_map( 'intval', $terms );
        $sql = sprintf(
            'FIELD( %1$s, %2$s ) ',
            $field,
            implode( ', ', $terms )
        );
        remove_filter( current_filter(), $orderby_terms );

        return $sql;
    };
    add_filter( 'posts_orderby', $orderby_terms, 10, 2 );
}
add_action( 'pre_get_posts', __NAMESPACE__ . '\wpse_91993_order_search' );

But that will ignore pages and attachments which are considered by default in the WordPress search query. Usually there aren’t even registered for the taxonomy category. At this point a proper solution depends on some decisions you need to make:

• Is it possible to register the taxonomy category to the post types page and attachment and make sure these posts get linked to at least the default term?
• Split your search in two queries, one for posts as shown above and one for pages and attachments and present the results separately in your theme?
• Is it worth the huge effort to change the SQL-Request to merge a selection on pages and attachments and a selection on posts ordered by terms? (I’m not even sure it is possible).