What you basically want to do is to change the SQL query being done to group the result of the query by category
The code taken from here groups by performing a sort by category. You can place the following code in your themes search.php file
<?php add_filter('posts_join', create_function('$a', 'global $wpdb; return $a . " INNER JOIN $wpdb->term_relationships ON ($wpdb->posts.ID = $wpdb->term_relationships.object_id) INNER JOIN $wpdb->term_taxonomy ON ($wpdb->term_relationships.term_taxonomy_id = $wpdb->term_taxonomy.term_taxonomy_id) ";'));
add_filter('posts_where', create_function('$a', 'global $wpdb; return $a . " AND $wpdb->term_taxonomy.taxonomy = \'category\'";'));
add_filter('posts_orderby', create_function('$a','global $wpdb; return "$wpdb->term_taxonomy.term_id DESC";'));
query_posts('');
?>
The rest of you search.php code should be something like
$catid = false;
while ( have_posts() ) {
the_post();
$cat = get post cat id
if ($cat != $catid) { // switching to posts from new category
display new categoty title
}
display post
}
The display logic might be more complicated if posts can belong to more then one category as it will be more difficult to decide to which category you are switching