I'm not sure about altering the way the search works, but I think you could implement a category search very easily.
The default search form might be something like
<form method="get" id="searchform" action="<?php bloginfo('home'); ?>/">
<p><input type="text" size="14" value="<?php echo wp_specialchars($s, 1); ?>" name="s" id="s" /> <input type="submit" id="searchsubmit" value="<?php _e('Search'); ?>" /></p>
</form>
What you could do is add a select element filled with your categories so that your search form would look like
<form method="get" id="searchform" action="<?php bloginfo('home'); ?>/">
<p><input type="text" size="14" value="<?php echo wp_specialchars($s, 1); ?>" name="s" id="s" />
<?php wp_dropdown_categories(); ?>
<input type="submit" id="searchsubmit" value="<?php _e('Search'); ?>" />
</p>
</form>
More info on wp_dropdown_categories
After this you would need to modify your search.php template to GET the category that was selected and only show search results from that category using a simple query_posts.
<p><em>You searched for "<?= $_GET['s']; ?>"</em></p>
<ol>
<?php
$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
query_posts(array('category__in' => array($_GET['cat']), 'paged' => $paged));
if (have_posts()) : while (have_posts()) : the_post(); ?>
<li>
<h2 class="post-title" id="post-<?php the_ID(); ?>"><a href="<?php the_permalink() ?>" rel="bookmark" title="Link to <?php the_title(); ?>"><?php the_title(); ?></a></h2>
<p class="search-meta"><?php the_time('F jS, Y') ?></p>
<?php the_excerpt(); ?>
<p><a href="<?php the_permalink() ?>" rel="bookmark" title="Link to <?php the_title(); ?>">Read more on <?php the_title(); ?></a></p>
</li>
<?php endwhile; ?>
</ol>
<?php endif; ?>
Be warned, I haven't actually tested this out, but that's what I'd try out straight up ;)
In fact I will be testing something like this a little later on, I'll come back here if it needs alteration!