There are several schemes for authenticating API requests, and they're different than normal authentication provided by plugins like restful_authentication or acts_as_authenticated. Most importantly, clients will not be maintaining sessions, so there's no concept of a login.
HTTP Authentication
You can use basic HTTP authentication. For this, API clients will use a regular username and password and just put it in the URL like so:
http://myusername:[email protected]/
I believe that restful_authentication supports this out of the box, so you can ignore whether or not someone is using your app via the API or via a browser.
One downside here is that you're asking users to put their username and password in the clear in every request. By doing it over SSL, you can make this safe.
I don't think I've ever actually seen an API that uses this, though. It seems like a good idea to me, especially since it's supported out of the box by the current authentication schemes, so I don't know what the problem is.
API Key
Another easy way to enable API authentication is to use API keys. It's essentially a username for a remote service. When someone signs up to use your API, you give them an API key. This needs to be passed with each request.
The downside here is that if anyone gets someone else's API key, they can make requests as that user. I think that by making all your API requests use HTTPS (SSL), you can offset this risk somewhat.
API Key + Secret Key signing
Significantly more complex is signing the request with a secret key. This is what Amazon Web Services (S3, EC2, and such do). Essentially, you give the user 2 keys: their API key (ie. username) and their secret key (ie. password). The API key is transmitted with each request, but the secret key is not. Instead, it is used to sign each request, usually by adding another parameter.
IIRC, Amazon accomplishes this by taking all the parameters to the request, and ordering them by parameter name. Then, this string is hashed, using the user's secret key as the hash key. This new value is appended as a new parameter to the request prior to being sent. On Amazon's side, they do the same thing. They take all parameters (except the signature), order them, and hash using the secret key. If this matches the signature, they know the request is legitimate.
The downside here is complexity. Getting this scheme to work correctly is a pain, both for the API developer and the clients. Expect lots of support calls and angry emails from client developers who can't get things to work.