Mine basically goes like this: (pseudocode)
GameState has:
- abstract Update(timePassed)
- abstract Draw(screen);
- abstract HandleEvents(events)
MainMenu IS-A GameState
Options_Root IS-A GameState
Options_AudioSettings IS-A GameState
Options_GraphicSettings IS-A GameState
Exploring IS-A GameState
InGameMenu IS-A GameState
Combat IS-A GameState
NpcDialog IS-A GameState
Most of those GameStates don't actually exist yet, because my game is still in development... So no Combat or NPC Dialog for example is actually working. But the GameState system itself is fully implemented and functional. 
Then my main loop goes:
while(game-is-running)
{
if(we-have-events)
{
currentGameState.HandleEvents(events)
}
currentGameState.Update(amountOfTimePassed)
currentGameState.Draw(screen)
}
And I basically have a stack of GameStates in an array. The GameState at the top of the stack is the active one.
So a GameState can push another GameState to the top of the stack, like Options_Root can push Options_AudioSettings to the top of the stack when you click the 'Audio Settings' button. A GameState can also pop itself from the stack, so Options_AudioSettings can pop itself (making Options_Root the top state again) when the 'Done' or 'Cancel' button is pressed.
...and there's other assorted features I have in the GameState class as well, but the above gives the overview of my architecture. This is the first game I'm doing this architecture in, so my implementation isn't quite battle-proven yet.
