First, just to make sure I understand "salting" correctly:
You randomly generate a string to append to the password before hashing it, so as to increase its length and make precomputed tables much less useful in cracking them.

Assuming my understanding is correct, then I'm having trouble how LinkedIn salted their passwords:

One of our major initiatives was the transition from a password database system that hashed passwords [...] to a system that both hashed and salted the passwords [...] That transition was completed prior to news of the password theft breaking on Wednesday.

Doesn't salting require you to have the plaintext password? How can you salt a hashed password?

-
According to media reports the Linkedin passwords have been stolen month ago and only recently published. So LinkedIn may be aware of the theft for quite some time. –  Hendrik Brummermann Jun 10 '12 at 21:07
Here is a SE link to an excellent explanation of cryptographic salts. It really helped me understand how they negate brute force attacks. crypto.stackexchange.com/a/1716/163 –  webworm Jun 16 '12 at 3:37

Basically, salting a password means that you compute a hash value which depends on the password and on a salt (a non-secret random value of sufficient length, e.g, 64 bits). Remember that salting a password allows to better resist attacks such as dictionnary attacks or time-memory tradeoffs (e.g., rainbow tables), i.e., attacks involving an offline pre-computation step, but not brute-force attacks.

If we denote by $H(.)$ the hash function ($\mathrm{SHA1}$ for LinkedIn), by $p$ the password and by $s$ a salt value, LinkedIn might find themselves in the situation where they have a database of values $h_i = H(p_i)$, for $1 \leq i \leq \ell$, where $\ell$ denotes the number of accounts. Thus, one could imagine that they compute $h^\prime_i = H(s_i||h_i) = H(s_i||H(p_i))$ ($||$ denoting a concatenation) and that they store the pairs $(s_i, h^\prime_i)$ in the database. Note that they don't need to know the passwords to perform this operation.

Another possibility would consist in resetting all the accounts, force the users to setup a new password, and hash them according to a better scheme, but this a bit less customer-friendly...

-
Another possibility would be to update the database whenever somebody logs in. I.e. they keep the $h_i=H(p_i)$, and when user $U_i$ sends his password $p_i'$ to log in, they check whether $h_i=H(p_i')$ and if that's the case they compute the salted hash. This way they are not limited in their choice of a hashing scheme, however it might take a long time until all accounts are migrated to the new hashing scheme. –  Maeher Jun 10 '12 at 10:06

There are two common approaches in practice:

• on login, the user enter his password into the login form. Therefore it is available in clear and can be used to for a different hashing method.

• the old hash can be used as input to the new hash function with salt hash_with_salt(old_hash(password)). This can be done at any time for all accounts.

The second approach requires that both hashes are calculated on every login. And it is incompatible with other systems that use the same hash_with_salt-function.

-
I'd go with the second unless your website regularly deletes inactive users. For a typical website I'd expect most users to be inactive. –  CodesInChaos Jun 11 '12 at 9:56