Does your theme have a search.php and a search-form.php ..
search.php will hold the markup around the search form (you can use the default theme for an example).
search-form.php will hold the form markup, the inputs etc, if you don't have one create it..
Place something along these lines in there.
<form method="get" id="search" action="<?php bloginfo('url'); ?>">
<label for="keywords">Search:</label>
<input type="text" name="s" value="Search" id="keywords" />
<input type="submit" value="Go" />
</form>
Then all you need do is add a couple of tag inputs..
<input type="checkbox" name="tag[]" value="tag-one-name" />
<input type="checkbox" name="tag[]" value="tag-two-name" />
Totally untested, but i believe that should work... above 2 lines go wherever you like (inside the <form> code </form> of course)..
If that doesn't work, let me know and i'll go test the code..