How did LinkedIn "salt" all their passwords? 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?
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...