You would have a single template that has the header and footer information. When a form is created the header and footer on the template would appear. The downside is if you change the header and/or footer then the template would have to be applied to each of the form designs to reflect the update. Your other option is to use fragments but the form author would be responsible to add the header and footer fragments to their form design. To ensure this occurs you could have the Adaptive Form to go through a review process using Form Manager prior to the form being published to production.
Could we have a Master template with just header and footer and all Templates are derived out of it?
No. There is no concept of 'template' of 'template'.
But you can do that, if you are on 6.2. You can go to template editor and create an AF template. And keep header and footer locked in 'structure' layer, so no author creating form out of that template will able to modify it.
Also if you update the template header and footer, all forms created out of that template, will show updated header and footer.