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