It is difficult to search for users (in code) based on profile information in Drupal 6 due to the flexible nature in which the profiles module stores information. Basically profiles are stored in 2 tables.

mysql> select * from profile_fields;
+-----+------------+-------------------+-------------+---------------------+------+-----------+--------+----------+----------+------------+--------------+---------+
| fid | title      | name              | explanation | category            | page | type      | weight | required | register | visibility | autocomplete | options |
+-----+------------+-------------------+-------------+---------------------+------+-----------+--------+----------+----------+------------+--------------+---------+
|   1 | First Name | profile_firstname |             | General Information |      | textfield |      0 |        0 |        1 |          1 |            0 |         |
|   2 | Last Name  | profile_lastname  |             | General Information |      | textfield |      0 |        0 |        1 |          1 |            0 |         |                                          
+-----+------------+-------------------+-------------+---------------------+------+-----------+--------+----------+----------+------------+--------------+---------+                                          
2 rows in set (0.00 sec) 

select * from profile_values limit 4;                                                                                                                                                            
+-----+-----+---------+                                                                                                                                                                                       
| fid | uid | value   |                                                                                                                                                                                       
+-----+-----+---------+                                                                                                                                                                                       
|   1 |   1 | John    |                                                                                                                                                                                       
|   2 |   1 | Doe     |                                                                                                                                                                                       
|   1 | 115 | John    |                                                                                                                                                                                       
|   2 | 115 | Smith   |                                                                                                                                                                                       
+-----+-----+---------+                                                                                                                                                                                       
4 rows in set (0.00 sec)

With only one value per row it is difficult to create a generic function to search for multiple values at once. We could examine both tables and hard code a mysql function using multiple joins for each fid but that isn'r very reusable. Thankfully the mysql GROUP_CONCAT function comes to the rescue. Combined with a simple function to get profile field definitions it is possible to search for users based on profile information. Here are two simple functions I came up with that make it easy to search for users based on profile information in drupal

/**
 * dgs_get_profile_fields
 * @return array(name => fid)
 */
function dgs_get_profile_fields($category = null){
  if(isset($profile_fields)){
    return $profile_fields;
  }
  static $profile_fields = array();
  $sql = "SELECT * FROM {profile_fields}";
  $args = array();
  if(!empty($category)){
    $sql .= " WHERE category='%s'";
    $args= array($category);
  }
  $result = db_query($sql,$args);
  while($row = db_fetch_object($result)){
    $profile_fields[$row->name] = $row->fid;
  }
  return $profile_fields;
}

/**
 * dgs_search_profiles
 * @param(array(fieldname => fieldvalue));
 * @return an array of user uids
 */
function dgs_search_profiles($params = array()){
  //Example SQL
  //SELECT GROUP_CONCAT(fid,'=',value) as profile from profile_values GROUP BY(uid) HAVING profile like "%1=Gary%" AND profile like "%2=Varnell%";
  $profile_fields = dgs_get_profile_fields();
  $having = array();
  $args = array();
  foreach($params as $fieldname => $fieldvalue){
    $having[] = "profile LIKE '%s'";
    $args[] = "%" . $profile_fields[$fieldname] . "=$fieldvalue%";
  }
  $having = join('AND ',array_values($having));
  $result = db_query("SELECT uid,GROUP_CONCAT(fid,'=',value) as profile from profile_values GROUP BY(uid) HAVING $having",$args);
  $users = array();
  while($row = db_fetch_object($result)){
    $users[$row->uid] = user_load($row->uid);
  }
  return $users;
}

And here is a usage example

    $users = dgs_search_profiles(array('profile_firstname' => 'John','profile_lastname' => 'Doe'));
    print_r($users);

Which returns

Array
(
    [xxx] => stdClass Object
        (
            [uid] => xxx
            [name] => jdoe
            [pass] => xxxxxxxx
            [mail] => jdoe@somewhere.com
            [mode] => 0
            [sort] => 0
            [threshold] => 0
            [theme] => 
            [signature] => 
            [signature_format] => 0
            [created] => 1264712914
            [access] => 1318017735
            [login] => 1317926353
            [status] => 1
            [timezone] => -21600
            [language] => 
            [picture] => 
            [init] => xxxxx
            [data] => a:1:{s:13:"form_build_id";s:37:"form-xxxxxxxxxxxxxxxxxxxxx";}
            [form_build_id] => form-xxxxxxxxxxxxxxxxx
            [roles] => Array
                (
                    [2] => authenticated user
                    [3] => xxxxxxx
                    [5] => xxxxxxx
                )

            [profile_firstname] => John
            [profile_lastname] => Doe
        )

If you have a better solution please let me know, and as always feel free to comment.