public function getStoreCategories()
    {
        $helper = Mage::helper('catalog/category');
        return $helper->getStoreCategories();
    }

In app/code/core/Mage/CatalogSearch/Model/Advanced.php, replace the getSearchCriterias() by following functions:

 public function getSearchCriterias()
 
     {
     $search = $this->_searchCriterias;
              /* display category filtering criteria */
         if(isset($_GET['category']) && is_numeric($_GET['category'])) {
         $category = Mage::getModel('catalog/category')->load($_GET['category']);
         $search[] = array('name'=>'Category','value'=>$category->getName());
      }
      return $search;
     }

Replace the getProductCollection() by following function:

 public function getProductCollection(){
    if (is_null($this->_productCollection)) {
        $this->_productCollection = Mage::getResourceModel('catalogsearch/advanced_collection')
        ->addAttributeToSelect(Mage::getSingleton('catalog/config')->getProductAttributes())
        ->addMinimalPrice()
        ->addStoreFilter();
        Mage::getSingleton('catalog/product_status')->addVisibleFilterToCollection($this->_productCollection);
        Mage::getSingleton('catalog/product_visibility')->addVisibleInSearchFilterToCollection($this->_productCollection);
        /* include category filtering */
        if(isset($_GET['category']) && is_numeric($_GET['category'])) $this->_productCollection->addCategoryFilter(Mage::getModel('catalog/category')->load($_GET['category']),true);
        }
        return $this->_productCollection;
} 

   <input name="<?php echo $_code ?>" id="<?php echo $_code ?>" value="<?php echo $this->htmlEscape($this->getAttributeValue($_attribute)) ?>" title="<?php echo $this->htmlEscape($this->getAttributeLabel($_attribute)) ?>"  class="input-text <?php echo $this->getAttributeValidationClass($_attribute) ?>" type="text" />
            <?php endswitch; ?>
        </li>
        <?php endforeach; ?>

         <li>
<label for="category_search_field">Search by Category:</label>
<select name="category" id="category_search_field">
<option value="">-- Any Category --</option>
<?php foreach ($this->getStoreCategories() as $_category): ?>
<?php if($_category->hasChildren()): ?>
<option class="parent-cat" value="<?php echo $_category->getId(); ?>"><?php echo $_category->getName();?></option>
<?php foreach ($_category->getChildren() as $subcategory):
if($subcategory->getIsActive()) : ?>
<option value="<?php echo $subcategory->getId(); ?>"<?php echo ($this->getRequest()->getQuery('category') == $subcategory->getId() ? ' selected="selected"': "") ?>><?php echo $subcategory->getName(); ?></option>
<?php endif; endforeach; ?>
<?php elseif($_category->getIsActive()): ?>
<option value="<?php echo $_category->getId(); ?>"><?php echo $_category->getName();?></option>
<?php endif; ?>
<?php endforeach ?>
</select>
</li>