I'll describe how it is done in PenguFlip.
I've got 3 main "UIViewController" subclasses which, together, manage the whole game.
So, for the game, I've got the GameController. It's "view" property is Sparrow's "SPView" class (created in the "loadView" method).
For the menu I've got the MenuController, which displays the menu. Its "view" property contains what is displayed in the menu.
Last but not least, there's the ApplicationController, which glues together game and menu. It owns references to the game controller and the menu controller, and switches back and forth between them.
In other words: at application start it will activate menu controller and display its view. Some time later, the menu controller will inform the application controller that the user would like to start a game (probably with a delegate method). At that moment, the application controller stops the menu and tells the game controller to start the game.
The game controller will now create an SPView and the "SPStage" subclass that contains the game. Now, Sparrow can take over.
Again, some time later, the game will tell the application controller that the game is over -- and now, the same process is done the other way round. The application controller tells the game controller to stop the game (releases stage and SPView), and displays the menu view.
That might sound a bit complicated now, but it's really not different than handling any other "UIViewController" classes in Cocoa. The only difference is that you've got an SPView displaying the game instead of an ordinary UIView. (However, as you know, the SPView is a subclass of of UIView, anyway).
I hope that helps you a little bit!