Here's the info on using full-text searches
http://dev.mysql.com/doc/mysql/en/fulltext-search.html
You must be using a MyISAM table to use full-text searches and you must add a full-text index in the CREATE TABLE for the table, or add it later with CREATE INDEX.
If you don't use full-text searching then you'll need to do it the way you are now, but if possible I'd recommend that you only allow for wildcards at the end of LIKE operations, so this is OK
firstname LIKE '$firstname%'
but this could be very slow
firstname LIKE '%$firstname%'
To search on lots of columns just put your filter tests together with AND if all conditions must be met, or OR if any of the conditions must be met.
Sean Nolan