Fewer, less, and (un)countable nouns

The words less and fewer are a troublesome pair. There is a lot of variation in the way that people use them, but traditionalists insist that this is wrong and the two words are never interchangeable. What’s the difference? How does one decide which word to use? Let’s ask the grammar books: