I am a complete C++ newbie, and I' m reading You Can Do It! : A Beginners Introduction to Computer Programming by Francis Glassborow. I find it quite easy to follow for people without any programming experience (some knowledge of Python might help, though).

After getting the basics, I'll go on with Accelerated C++: Practical Programming by Example by Andrew Koenig and Barbara E. Moo.

Afterwards I plan to read C++ GUI Programming with Qt 3 by Jasmin Blanchette and Mark Summerfield, and finally, as time permits, other advanced C++ books (Alexandrescu, Sutter, Meyers, etc).