In terms of just C, I liked O'Reily's "Practical C Programming". There's also "Practical C++ Programming", which I also have -- it uses (nearly) identical text for the chapters where C++ is based on C, but the OO stuff is unique to the latter book. The C subject matter (the first half of the book) was written very well. The C++ subject matter feels a little tacked-on, but overall, it's still pretty good. If you're comfortable with C already, go elsewhere. If you want to start from the beginning, it's a really good book for that.
There's not much you need to learn, in terms of the language, for Atmel devices specifically. Bookmark the avrlibc site, you'll reference it a lot. You do need to be able to read and understand the datasheet sections on the peripherals you're interested in (e.g., timers and UARTS, etc.) If you can read the datasheet and figure out what code is required to (e.g.) turn off the watchdog timer, you're in good shape.
Learning a programming language (or a new microcontroller) is an exercise in immersion, just like a spoken language. You need to devise a project that is SIMPLE and ATTAINABLE, and will keep you interested enough to provide the motivation to get through initial hurdles. Hello World will teach you how your IDE / compiler works, and what a minimal C program looks like. Then, it's up to you to find your bliss. For me, it was 1) learning how to open a WAV file and show the metadata; then 2) learning how to open an audio device; and 3) learning how to play the audio data from a file. That was my intro to C, and I'm still working on that project to this day -- but, obviously, now it does a lot more.
From my example, you can tell I learned how to program on a PC rather than a micro. If you're just starting out with C, you might want to get your bearings with Linux and GCC, or Windows and Visual Studio Express, or Mac and Xcode. The write / build / debug cycle is a lot easier when you have a full dev environment. If you're already used to coding from the Arduino, then you're probably good to go.