What kinds of things are changing?
Pretty much all styles have changes, and the generic layout as well. For instance, our old template used to have the headers in different text boxes from the body and now they will be in the same text box as the body.
You can just edit the styles, but if you are changing page sizes you probably want to remake the template. Otherwise, just edit the master pages.
I'm guessing you mean headings, not headers (which would be at the top of the page). Were they threaded with the body text before? Anchored? Free-floating? It's pretty painless, for example, to export a story to InDesign Tagged Text and place that in a new file (or the same file). It will bring the styles with it.