Storing the cookie should be a quick and easy work around. Maybe you don't have an editable region in your header or you didn't copy the necessary code from the header to the page where you want it to work.
I would suggest persuing the cookie route and try to figure out why it isn't working. A good first step is to post the url to the page that is broken and somebody can look at it for you if you can't spot the problem.