This is just personal preference obviously but I would go and start playing around with some of the established engines out there. Then when you know them well enough, try their scripting and finally tinker with their code when you're familiar. That's how I learned anyway, but it limits you to the engines which have source or scripting.

I think it's really important that you can change stuff and see your results immediatly, which isn't always the case if you program from the ground up where you have to put in a lot of ground work before you see any results.

Good luck!

You can start by learning C++ with any book that has good reviews on amazon.
Once you have learned all the core concepts of C++, then start checking out engines
and see how they work behind the scenes.

You can start by learning C++ with any book that has good reviews on amazon.

If you are a beginner i would avoid the for dummies C++ book, it seemed to me at least as though it jumped straight in, even though it claimed to be aimed at people with no experience. "The beginning C++ through Game Programming" book isn't a bad one to start with and seems a lot more noob friendly that the dummies book i have.

If you find going straight into C++ a bit too demanding with all of it's memory management and whatnot, you may want to check out C# which can run managed code and that takes away some of the worries. After learning C# it will be much easier to go into C++, and also there are many engines that use C# (as scripting or otherwise) and allow you to get good results quickly. This is a suggestion if you like learning by trial and error, rather than reading a lot of theory and struggling to conceptualize how that is supposed to be useful down the line.

In my opinion, C# is a much better language than C++ because of managed code and the .NET framework. It is also supported by alot of game engines as a scripting language. This is just my opinion, its all up to you.

I started my first 3D c++ game after getting some experience with a 2D game in VB and Java. It was tough getting used to the language because I didn't really read any books... except maybe the "for dummies" book, which I would not recommend. But after going through the process of creating a game I feel more comfortable with C++. It just took a lot of tutorials and help, and I still don't have a "formal" understanding of the language.

If you find going straight into C++ a bit too demanding with all of it's memory management and whatnot, . . .

Actually, somehow I was able to completely avoid memory management for the first few months of making my first c++ game. I recently decided to restructure my game and all of the sudden I'm bogged down with memory problems. If you do decide to go straight into c++, then make sure your engine architecture avoids pointers. (especially raw pointers) Check out boost's smart pointers if you need them.

Edit: If you want to start from scratch and see results immediately, I would recommend NeHe's openGL tutorial. Starting with the graphics lets you experiment from the beginning, then after the first 10 or so tutorials you can start to work on the actual game.
http://nehe.gamedev.net/lesson.asp?index=01