The larger problem I'm having is getting it to 'stick' on a theme. Its fine once its changed, some links will hold, others will not.
I don't recommend that you define it just with cookies, allow it on there nonetheless as this way the user can have it stick for them. Otherwise, your looking at using sessions.
Now, without knowing what you have set within your tracking I cannot tell you the best way of doing this. From the given code that we have the only tracking I can see thats being used is to set a cookie, not to read information after the fact. As I mentioned, cookies are also unreliable for generating information.
What I would do is like so:
Just change whatever you are using to identify the css type from $_COOKIE to $_SESSION and it should work no problem for you. Of course, I haven't tested this though, so give it a shot somewhere where it won't cause you headaches first :P
ini_set(session.use_trans_sid, '1'); // Think this is right, I always have them enabled so I don't need to set it (try it without this line first, with cookies off)
// Strongly recommend the use of this to confirm that the user isn't trying to pass their own data:
$allowed_styles = array(
// Style is currently empty, let us check the request methods:
if (!isset($_POST['style']) AND isset($_COOKIE['style']) && in_array($_COOKIE['style'], $allowed_styles))
// Cookie is set for this style:
$_SESSION['style'] = addslashes($_COOKIE['style']);
else if (isset($_POST['style']) && in_array($_POST['style'], $allowed_styles))
// Cookies not set (or possibly set due to first condition) however post is set:
$_SESSION['style'] = addslashes($_POST['style']);
// Neither cookies, sessions, post, or allowed data is set, let us default it:
$_SESSION['style'] = 'default';
setcookie('css', $_SESSION['style'], time()+999999);
// Here, you will need to have whatever code to identify the page's css type