I don't agree on any of the programming book recommendations. All books on programming languages are filled with the author's own biases and in some cases, lack of proper research. K&R may be good for C, but it's not something you should start with.
I'd recommend that people start learning a language without the aid of a book, but by reading other people's code and using grep and the man page for any function that they don't understand. Start by reading simple programs, and modifying them to suit your own needs.
Once you've gotten some distance into the language, that's when you can pick up books. My favourites would be the "Practice of Programming" and the "Elements of Programming Style". Neither are language specific, and both are excellent regardless of the language you're using.
"Programming Pearls" and "More Programming Pearls" by Jon Bentley are also great, are again language independent, and have stood the test of time.
When you've moved sufficiently high up the ladder, and your brain is in high absorbant mode, pick up the "Art of Computer Programming".