Just to add some details to the existing answers...
my question is how would the client know to generate a random 256 bit key? (Why not 128?).
This depends on the the cipher suite that is negotiated. The list of those defined as part of TLS 1.1 is in RFC 4346 Appendix A.5. For example
TLS_RSA_WITH_AES_128_CBC_SHA will use a 128-bit key, whereas
TLS_DHE_RSA_WITH_AES_256_CBC_SHA will use a 256-bit key.
Which cipher suite is negotiated will depend on the client and server configuration, not on the certificate installed on the server. When the client initiates the connection with a
Client Hello message, it sends a list of cipher suites it supports. The server then picks the one it wants and says so in its
Server Hello message.
This cipher suite then determines how these symmetric keys are eventually shared. The immediate purpose of the SSL/TLS handshake is to establish a share pre-master secret between the client and the server. This is more broadly referred to as the key-exchange (see RFC 4346 Appendix F.1.1).
This falls in two categories (excluding anonymous key exchange):
- RSA key exchange (e.g.
TLS_RSA_WITH_AES_128_CBC_SHA): the client encrypts the pre-master secret using the server's public key (found in the certificate).
- DH(E) key exchange (e.g.
TLS_DHE_RSA_WITH_AES_256_CBC_SHA): a Diffie-Hellman key exchange takes place. The server signs its DH parameters and the client verifies the signature against the public key in the server certificate. (Having an RSA-based certificate doesn't imply an RSA key exchange.)
At the end of the handshake, whichever of these two steps were used, the client and the server are in possession of a common pre-master secret, from which they derive a master secret (see RFC 4346 Section 8.1).
From that master secret, both parties can derive the encryption keys (and MAC secrets), as described in RFC 4346 Section 6.3.
Besides the key type (RSA or DSS), there is nothing in this that makes the size of the encryption key depend on the certificate. In addition, both types have cipher suites that use 256-bit keys: for example
TLS_DHE_RSA_WITH_AES_256_CBC_SHA. (DSS is a signature-only algorithm, so you wouldn't get an RSA-like key exchange to encrypt the pre-master secret.)
The size of the key in the certificate only matters to prevent forgery of the key exchange (or to be able to decipher recorded traffic back): if someone was able to find the private key from the public key in the certificate, they could act as a MITM to impersonate the real server or they would be able to decipher the enciphered pre-master secret (and thus the recorded traffic) when using an RSA key exchange (DHE cipher suites are precisely designed to prevent getting access to the pre-master secret, even if the attacker gets hold of the private key and the recorded traffic, see this question). This is why a sufficient large asymmetric key matters.
Certification Authorities tend to put "256 bits" on their websites because it looks good from a marketing point of view.
It's not wrong, but it can be misleading for people who don't understand that it's how your server is set up and what your clients support that matters.