> Headers and footers are typically not a lot of bytes on the wire, so there's not a huge savings.

In that case just flip it-- give links as data urls which hard-code the header/footer and which use a client-side include for the content. :)

Old links eternally provide the navigation the users know and love!