First You go Admin Side.
1. Select your catalog ==> Manage Attributes ==> Edit Attributes
2. Then Frontend Properties Use in Advanced Search is YES or NO
now you can see the frontend advanced search tab.
And one more update you can use below link for categories added in advanced search.
http://www.magentocommerce.com/wiki/5_-_modules_and_development/search_and_advanced_search/how_to_add_search_by_category_to_advanced_search
that is all.