Search taxonomy terms with node_search_execute()
Actually, the only missing part is the form field that should allow the users to select the taxonomy terms used from the nodes they are looking for. The code used from Drupal 7 (and Drupal 8) is still looking for the corresponding values in $form_state['values'].  

If you look at the code used by node_search_validate(), the form validation handler added by node_form_search_form_alter(), you will notice the following lines.

  if (isset($form_state['values']['term']) &amp;&amp; is_array($form_state['values']['term']) &amp;&amp; count($form_state['values']['term'])) {
    $keys = search_expression_insert($keys, 'term', implode(',', $form_state['values']['term']));
  }


If you then look at the code used by node_search_execute(), you will notice the following lines.

  if ($query-&gt;setOption('term', 'ti.tid')) {
    $query-&gt;join('taxonomy_index', 'ti', 'n.nid = ti.nid');
  }


Effectively, the functionality of searching those nodes that use specific taxonomy terms has not been removed; it has been hidden to the users who don't have anymore a way to tell the Node module to which taxonomy terms they are interested. This seems rather unintentional; probably the feature was supposed to be completely removed, but the submitted patch removed just the code for the user interface. I cannot find the related issue opened on Drupal.org, and I cannot say if my supposition is correct.

Until the code in node_search_execute() and node_search_validate() is not changed, all you need to do is adding the form fields in the search form, keeping in mind that the Node module is looking for $form_state['values']['term']. (In other words, the form field added for selecting the taxonomy terms should be in $form['term'].)

If, and when, that code is removed, adding that form field would not have anymore any effect.
Drupal doesn't allow a module to alter how a module integrates with the Search module. As a matter of fact, Drupal uses hook_search_info(), but no hook_search_info_alter(); if you would want to extend how searching a node is done (for example, by adding more options), you would need to alter the page callback assigned to search/node and search/node/%menu_trail. See search_menu().