How long shall a certificate be valid?

The expiration date for a certificate should be set to the date at which you would like the certificate owner to come back for a renewal. This is a matter of trade-offs:

• Each renewal operation entails some action from some human somewhere, so it has a cost which can be non-negligible.
• Commercial CA use a business model which entails selling certificates, and frequent renewals mean more income.
• Expiration of certificates allows you to remove the corresponding entries from CRL (Certificate Revocation Lists) so you do not want to make certificates live really long.
• Some jurisdictions mandate specific validity ranges for reasons which are often obscure and sometimes wholly irrational. But the Law is the Law.
• You do not want to make certificates whose life extends beyond the date at which you estimate that the public key might become crackable due to technological advances.

There are various "estimates" for "key strength" depending on its length, and these sometimes come with recommendation of key lifetime. This kind of job if 10% science, 90% "educated guesswork", which is a kind of divination. See this site for a lot of data. In particular, NIST says that a 2048-bit RSA key ought to be fine until at least year 2030. But the difference between a "maybe crackable key" and a "maybe not crackable key" is very fuzzy, so don't expect hard data here.

In practice, key strength far exceeds actual certificate lifetimes. Typical lifetimes for end-entity certificates range from one to three years; make that five to ten years for intermediate CA. For a root CA, make it expire in 2037 (i.e. as far as possible in the future but without crossing the fateful Y2038 problem).

There's some info in the Microsoft blog:

Key length of 1024:  Validity period = not greater than 6-12 months
Key length of 2048:  Validity period = not greater than 2 years
Key length of 4096:  Validity period = not greater than 16 years

Edit :) ok, so let's try some more:

There is this recommendation from US government that says that shouldn't be longer than 3 years. And the validity period should be related to the interaction necessary to "renew" it: the more human interation is necessary, the longer the time, up to 3 years.

In Brazil, the recommendation is: source

• 1024 bits, software generated: 1 year if stored in software and 2 years if in hardware (token)

• 1024 bits, hardware generated: 3 years if stored in hardware