Search Form Functionality

I am looking at creating a directory site using WordPress and have a couple of queries that hopefully someone could clear up for me.

I have had a think about how the listings would be organized found it will be simple enough having them as posts under each category. I will need to add some sort of search function to the site, something similar to the one in the header of this site: http://www.businessclassified.co.uk although there are 3 fields on there, the site i am creating will only need 2 but both will need to be completed in order for the search to work.

I was wondering if this would be possible to achieve in WordPress? If so what would be the best way to go about it?

Any Help is much appreciated