It's perfectly doable, but if you have to ask, you're probably better off creating a new Navigation-based app and copying your view controller and its .xib over to the new project.
Anyway, assuming the navigation controller is the first thing people see, you'll have to open your MainWindow.xib and add a navigation controller to it. Then add a navigation controller outlet to your app delegate and connect them. Then you'll need to set the navigation controller's view as your main window's view.
You can add a table view to any iPhone app fairly easily, just by creating a new UITableViewController subclass from the File -> New command.
Even if you go this route, I would suggest creating a new navigation-based project to use as a template/cheat-sheet.