You can use hook_form_BASE_FORM_ID_alter() hook to add your HTML to the existing markups,
/**
* Implements hook_form_BASE_FORM_ID_alter();
*/
function <MODULE_NAME>_search_block_form_alter(&$form, &$form_state, $form_id) {
//Reffer prefix from the api to add <span> or <label>
// https://api.drupal.org/api/drupal/developer%21topics%21forms_api_reference.html/7#prefix
// Reffer prefix from the api to add </span> or </label>
//https://api.drupal.org/api/drupal/developer%21topics%21forms_api_reference.html/7#suffix
}