The best thing you can do is use a database like MySQL (or any will work) to store the employee info.
When someone searches you just tailor your database query to fit their query and echo out the results.
The result will just print a link to that employees normal profile page.
As usual I make it sound easier than it probably is, hehe.
As long as you don't have complex search criteria, it shouldn't be too hard.
Your best start is to find a few articles here on best practices for databases.
Tim Purdue has a few really good ones.
