I have tried having a stack of states before, where new states get pushed on or popped off. This means you can have an options state pushed on, and then just pop it off to reveal the previous state with the back button is pressed. Its probably a better idea if you've got lots of layered dialogs (an RPG inventory perhaps?) but it can get a little confusing.
The stack also means you can keep states in memory instead of recreating them each time, but theres no reason why you couldn't get the same effect with the first method and a pool of created states.
I combined several things in my last framework (not necessarily better, but I found some of them particularly neat in practice):
NB: there was no explicit stack
- "default" state. Whenever a state exits and doesn't specify a new state to takeover, the default state takes over. Useful in lots of situations to have a top-level/root node that always takes over if needed
- delegateToState( ... ) causes the specified state to take over implicitly pushing the current state onto the stack (makes it a bit friendlier for people not accustomed to using stacks

)
- switchToState( ... ) as for delegate, except does NOT push the current state onto the stack
- exit(). Depending upon how this state started, exits this state and chooses a different one (c.f. previous items)
I think there were some other things, but IIRC I found that the above simplified options were actually enough to do everything I wanted, and were a little easier to maintain than a stack (because the relationships between states were more explicit in the source code, and didn't place such a burden on the reader of mentally keeping track of the stack...)
One of my aims was making the source easier to understand "at a glance".