If you don't mind a reference to a book, there's an article named "Large-Scale Stack-Based State Machines" in [Game Programming Gems 5](http://www.amazon.com/Game-Programming-Gems-CD-v/dp/1584503521) which provides a very good implementation of what you seek. I've been using a variation of it for the last few years, and like it a lot. Most of the insights that I got from that article, I've already talked about [in this answer](http://gamedev.stackexchange.com/a/25857/11686), so there's no need to repeat myself.

<strike>But since it might not be easy to get your hands on that book, here's a free alternative. The [first chapter of the Gamebryo Textbook](http://goo.gl/Yr5Q0) describes an implementation which is pretty much based on the one presented in Game Programming Gems 5, and you can also find the [source code here](http://goo.gl/kKDTb).</strike>

(Update: The links above are no longer valid, and I can't seem to find where they have been relocated. If someone does, please edit this answer)

And finally, despite being in C# and XNA, [this sample from Microsoft](http://create.msdn.com/en-US/education/catalog/sample/game_state_management) provides a simple implementation which should be pretty easy to follow and convert to C++.