Filtering Search Results by Tags

I am working on a client website that needs to have an advance search option that allows for selecting tags via checkboxes and then doing a search based on the selected items. The functionality I’m looking for is similar to http://wordpress.org/extend/themes/tag-filter/.

Any ideas on how to do this? I’m able to do it based on categories, but haven’t figured out how to do it based on tags.