Well, I got intrigued by the idea so I put something together. Its not exactly what you are hoping for I guess, but its the idea I presented. There should be plenty of comments everywhere so you can see how you would use it.

The javascript and cookie portion is old school stuff and 4.0 browsers won't choke on it, but note that because it relies on CSS its really intended for more modern browsers.

I have attached a zip with all the relevant files, just unzip them to a single directory for a working example. Here's a live version if you want to get an idea of how it works first.

http://speculativevision.com/cookiecss/

I have never really tried to use different themes in LinksSql so I'm not sure what might be involved. My understanding is that the primary method is to pass a different template name to the dynamic page generation script yes? If so, I'm sure it is possible to use perl to set and read a cookie then alter the links to use that cookie's value for the page template name as you move from page to page. Unfortuately I don't know perl or the links scripts well enough to tell you how to do that.