Please Note: This is only for Services 1.x and 2.x. See kylebrowning's suggestion here for 3.x:
http://drupal.org/node/1118366#comment-4312286

Services offers the ability to control access via API keys. This requires
setting up a key on the remote server, and putting together a specially
crafted call on the requesting server. This document gives an example of how
to set this up in Drupal using the user.get service.

On the remote server:

1) Install Services, enable the Services, XMLRPC Server, System Service, Key Authentication, and User Service
modules.

2) When using API key authentication, Services runs as the anonymous user, so you will need to modify the anonymous user's permissions as necessary. For this example, you will need to give the anonymous user 'get own user data' (under user_services module).

3) Now you need to create an API key and give the key access to the methods you want it to use. Go to Administer->Site Building->Services->Keys->Create Key. Give the key a title and a domain. The domain can really be anything, but typically it will match the external domain which has permission to use this key. Next, under 'Method Access' check the specific methods you want this key to have access to. Note that if you activate additional service modules you will need to use Keys->List->Edit to add the additional methods to the key. Submit the form. You will now see your key listed. Take note of this key as you will need it in the code you are about to write.

4) Go to Administer->Site Building->Services->Settings and choose 'Key authentication' from the drop down list labeled 'Authentication module'. All services calls are now required to include API key information.

On the requesting server:

Service calls using API keys require four parameters:

Timestamp - Current time in Unix timestamp format.
Domain - The value you entered for domain above.
Nonce - A random value.
Hash - An sha256 hash of the timestamp, domain, nonce and remote method name delimited by semicolons and using the remote API key as the shared key.

Here is some example Drupal code which shows how this works.

$domain = 'my domain';
$timestamp = (string) time();
$nonce = user_password();
$hash = hash_hmac('sha256', $timestamp .';'.$domain .';'. $nonce .';'.'user.get', 'remote_api_key');

// If your drupal installation is in a subdirectory, the following url should be
// http://<domain>/<directory>/services/xmlrpc
$xmlrpc_result = xmlrpc('http://remoteserver.com/services/xmlrpc', 'user.get', $hash, $domain, $timestamp, $nonce, 0);
if ($xmlrpc_result === FALSE) {
  print '<pre>' . print_r(xmlrpc_error(), TRUE) . '<pre>';
}
else {
  print '<pre>' . print_r($xmlrpc_result, TRUE) . '<pre>';
}

Some notes:

1) The timestamp must be cast to a string or you will get an error that you are passing an argument of an incorrect type.

2) Drupal's user_password() function is a convenient way to generate a random string to use as the Nonce.

If this code runs successfully, then you should see the anonymous user's information printed. Otherwise you will see an error.