In my state machine there are two ways to change state:
1) Push the new state onto the state stack
2) Change the top state on the state (basically a pop followed by a push)
That way you can have the main menu push the play state onto the stack, and when the game ends and the play state gets poped, you'll automatically get back to the main menu.
You can also eg. have a paused game state. When resume the game again, the paused state gets poped and you're back in the game again.
When the player selects "Quit" from the main menu, the menu state gets poped, and since there are no more states on the stack, the game ends.