It depends on how much you want to separate roles.
Basic system: your "signature" is a MAC. The "API key" is a secret value with is shared between the server and the user. Normal MAC algorithms like HMAC can use arbitrary sequences of bits as key, so a key is easily generated by using /dev/urandom
(Linux, *BSD, MacOS X), calling CryptGenRandom()
(Win32) or using java.security.SecureRandom
(Java).
Enhanced system: your signature is a true digital signature. This makes sense if you want to separate the key generator (who can produce keys which will be accepted by the server) from the server itself (who validates the incoming signatures). Keys for signature algorithms are mathematical objects with a lot of internal structure, and each algorithm implies a specific key generation algorithm. Use a library which already implements the needed bits (e.g. OpenSSL).
Either way, there is more to it than just key generation and signatures. For instance, you probably want to avoid replay attacks: an ill-intentioned third party spies on the network, and records a valid request signed by a regular user. Later on, the attacker sends the request again, complete with its signature, so as to replicate the effect. To avoid replay attacks, you must add some sort of external protocols, and these things are hard to do (it is not hard to define a protocol; it is very hard to define a secure protocol). Therefore, the smart thing to do is reusing an existing, well-vetted protocol, which, in practice, means SSL/TLS.
With SSL, the "basic system" is reduced to sending the API key in a header at the beginning of the conversation (that's exactly what happens with password authentication on HTTPS Web sites). The "enhanced system" is then "SSL with a client certificate".