There are a couple options to add searching and a category list. One is a template such as cMap which has both searching and a category filter. The other is the Widget Pack. It has widgets for both search and a category list that can be added to the theme’s side bar. You could even use both cMap and the widgets if you wanted.
I hope that helps!