Username and passwords:
Upsides: Easy, and usually needed in the first place
Downsides: Only secure over HTTPS or with digest authentication; slow and can't use digest auth if passwords are properly strongly hashed.
Tokens / API Keys:
Upsides: Easy to check, can be structured to separate 'device authorization' from 'authentication' -- if users have multiple devices or sessions and you'd want to disable some without requiring re-login, this is a plus.
Downsides: You still have to authenticate, which means a username and password. If you use OAuth2, it's a huge, badly written, hard to understand, incomplete spec.
HMAC:
Not actually an authentication mechanism, though usable as a primitive to start building one.
SSH or other public/private keys:
Upsides: Can be securely set up with nearly no user intervention; easy to check; can do device authorization if you structure it right. You use an HMAC+signature over part or all of the request to authenticate it. Faster than verifying a strongly hashed password.
Downsides: requires some crypto understanding. Not supported in browsers.
Note: check out
https://github.com/joyent/node-http-signature/blob/master/http_signing.md