How can I allow users to search for other users based on profile information
You can achieve this by using views contextual filters.

or you can use advanced search for users 

http://www.yoursite.com/search/user


set the user permission accordingly to view advanced search