How to hook into Drupal 6 search process?
If you look at search_menu(), you will notice the following code.

  foreach (module_implements('search') as $name) {
    $items['search/' . $name . '/%menu_tail'] = array(
      'title callback' =&gt; 'module_invoke',
      'title arguments' =&gt; array($name, 'search', 'name', TRUE),
      'page callback' =&gt; 'search_view',
      'page arguments' =&gt; array($name),
      'access callback' =&gt; '_search_menu',
      'access arguments' =&gt; array($name),
      'type' =&gt; MENU_LOCAL_TASK,
      'parent' =&gt; 'search',
      'file' =&gt; 'search.pages.inc',
    );
  }


Every module implementing hook_search() gets a menu tab. So, your module will be asked to search only when the users select its tab.