With regard to SEO, the content of the site may not be accessible to crawlers unless you provide a means of distinguishing crawler traffic from human users. You could parse the user agent string and allow traffic from search engine crawlers to bypass the age gate. Ordinary users would not know how to exploit this to not have to verify their age, so I don't think this is an issue. For Google, see http://support.google.com/webmasters/bin/answer.py?hl=en&answer=1061943. Otherwise, if the crawler can access the page, there should not be a significant impact on SEO (but see below).
With regard to how to store this information, doing it server-side requires a means of identifying the computer users are accessing the site with, so this isn't really an option. The only other realistic choice is HTML5 Local Storage, which won't work with older browsers, so cookies are probably the best way to go.
Coding the age gate into the header of the index will not work for other pages. You could reference the code in every page of the site which must remain behind the age gate, which this would make it easier for crawlers to read the content, but you must remember to place the reference on every page on the site which requires it, and the age gate may end up in the search engine's index, which may not be what you want.