Modify the "no content matched your criteria" message in Genesis

functions.php

<?php

// do not include the opening tag

add_filter( 'genesis_noposts_text', 'leaven_change_search_text_one', 10, 2 );
function leaven_change_search_text_one( $text ) {
	$text .= __( ' Would you like to try again?', 'leaven' );
	$text .= get_search_form( false );

	return $text;
}

add_filter( 'genesis_noposts_text', 'leaven_change_search_text_two', 10, 2 );
function leaven_change_search_text_two( $text ) {
	$text  = __( 'This is completely embarrassing. I have no posts to show you. Care to search again?', 'leaven' );
	$text .= get_search_form( false );

	return $text;
}

add_filter( 'genesis_noposts_text', 'leaven_change_search_text_three', 10, 2 );
function leaven_change_search_text_three( $text ) {
	if ( is_search() ) {
		$text = __( 'This is completely embarrassing. I have no posts to show you. Care to search again?', 'leaven' );
	} elseif ( is_archive() ) {
		$text = __( 'Evidently I don\'t have much to say on this topic. Maybe you\'d like to search for something else.', 'leaven' );
	}
	$text .= get_search_form( false );

	return $text;
}

Very helpful, thank you!

Is there a way to insert a heading on the page, apart from the modified text?