Bainternet's answer gives you the number of users for one query and doesn't help if you need multiple pages of users.
If you have thousands of users that's not what you want. You can use WP_User_Query much the same way you use WP_Query for posts. It's very similar to get_users -- same arguments, but different features and usage.
Most importantly you can get the total number of users who match your criteria without actually returning all of the results (and potentially hitting memory limits).
Usage
$user_query = new WP_User_Query(array(
'number' => 15,
'paged' => 1
));
$users = $user_query->get_results(); // array of WP_User objects, like get_users
$total = $user_query->get_total(); // int, total number of users (not just the first page)
Examples:
echo $users[0]->get('display_name');
// "Radley Sustaire"
echo count($users);
// "15" (count from the first page of users)
echo $user_query->get_total();
// "86" (count from all pages of users)
$num_pages = ceil( $user_query->get_total() / 15 );
// "6" (number of pages of users. 15 is the "users per page" from the first example)
// (* do NOT use count($users) in place of 15. try a separate $per_page variable)