For the server certificate: the cipher suite indicates the kind of key exchange, which depends on the server certificate key type. You basically have the following:
For TLS_RSA_* cipher suites, key exchange uses encryption of a client-chosen random value with the server's RSA public key, so the server's public key must be of type RSA, and must be appropriate for encryption (the server's certificate must not include a Key Usage
extension that says "signature only").
For TLS_DHE_RSA_* cipher suites, key exchange uses an ephemeral Diffie-Hellman, and the server signs its part of the DH key exchange with its RSA key. So the server's public key must be of type RSA, and must be appropriate for signatures (there again, the certificate must not restrict the key usage to only encryption).
TLS_DHE_DSS_* and TLS_DHE_ECDSA_* cipher suites use an ephemeral Diffie-Hellman key exchange, and the server's key must be of type, respectively, DSA and EC, and must be appropriate for signatures.
TLS_ECDHE_* cipher suites are similar to TLS_DHE_* cipher suites, except that the Diffie-Hellman key exchange is an elliptic curve variant. Conditions on the server's certificate remain the same.
TLS_DH_* and TLS_ECDH_* cipher suites are different (mind the lack of 'E' after the 'DH'). For these suites, the server's certificate directly contains a Diffie-Hellman public key (or an elliptic curve variant thereof), and the cipher suite then qualifies the algorithm used by the issuing CA to sign the certificate. For instance, TLS_DH_RSA_* means "server has a DH public key stored in a certificate that was signed by some CA with RSA". This is the only case where the signature type on the certificate has any relation with the cipher suite. Since in practice nobody uses that kind of certificate, this case can be neglected.
For the client certificate: the client presents a certificate when the server asks for it. The client certificate type has no relation whatsoever with the cipher suite (except for the extremely rare case of static DH certificates, but I have never seen that used in practice). The client certificate must be appropriate for signatures. As part of the handshake message that requests a client certificate, the server sends some information about the supported algorithms (see the standard). In fact, TLS 1.2 further expands that mechanism by giving a flexible list of supported algorithm and hash function combinations.