I am thinking of using the superfish menu module. The site will have three levels of navigation. Any tips for creating the nodes/pages so that the Menu structure works out properly? Or as long as I create all the level one pages and then use them as the parent menu for any child pages, will the menu be generated ok?
You can always rebuild the menu, so I would just start adding content and organizing the links. The main advantage of a CMS like Drupal is that you are not "locked in" to a specific configuration and you can always change it around freely at any time.
One thing to be careful about is that the deeper your navigation structure, the harder it is for users (particularly older users and those not skilled in using mouse, etc. as well as those on mobile devices) to use the menus, but this is something you can only find out once you actually build the menus and do usability tests.
As you note, you will need to first create the parent pages before you can add links underneath them to the child pages.