How do I create a default global header and footer for entire store network?

Building GridMarket, MartketPress store network. Header and footer serve primary site only, so how do I keep them consistent throughout all stores? (Can "new blog templates" do this, or does it just work for page templates?)

Header: How can I add my custom-logo into the php script so I don't have to load my logo for each new site, i.e. header.php.

Footer: Can I customize footer.php - what is the best way to address these elements:

a) Make copyright work for and link to primary site homepage only.

b) Footer1, Footer2 columns are just text "html weblinks" for about, contact, help, policies. Where/how can I add this into footer.php?

c) Footer3 is a "menu" of 3 blog categories. Is there a way to add/link this menu in?

d) Footer4 is recent comments for primary site.

I could leave out c) and d) if I have to.

Thanks.