I would always recommend going for master pages first. This allows you to get all of your common elements (header, navigation, footer) etc. done in one place. You can find some information about how to progress here: Creating portal engine master pages.
If you're not at the point where you're ready to build your master page, you can always use one of the provided ones - such as the blank master template - as this will allow you to ge the inheretance right so that once you are ready to build your master page, you need only to update the templates used on the site root (for example). By reading your question though, I think you're ready to build the master page already.