I read The Waite Groups 'C Primer Plus' 3rd edition. It was a very good book. It goes into a good amount of depth. There are easier books to start out with but if you can handle this one than you will have a good understanding of 'C' by the time you finish reading it.
That's the same book I just got. I'm into chapter 2 already:D
The "Teach Yourself in 24hrs/21days" series are good to have as a reference, but they are limited in terms of what they can teach you. Still Check out "Teach Yourself C"/C++" as they are great when you want to look up something quickly.
I used "C: How to Program" 2nd Ed. by Deitel and Deitel to learn the basics. It was okay, but it did tend to move a bit quickly for the beginner. The other book I used was "Data Structures and Program Design in C" 2md Ed. by Kruse et al. I don't recommend this book to anyone who does not already have a thorough understanding of C program structure and syntax, as it makes the assumption that you are a software engineer in training.