No es recomendable usar cookies porque algunos navegadores no lo admiten por defecto. Bueno, lo que puedes hacer como te dije es usar sesiones mediante ajax.
En primer lugar al cargar una página debe imprimirse en el elemento body lo siguiente:
Código PHP:
<?php
$color = $_SESSION["col"];
?>
<body <?php if ($color) echo "onLoad=\"cambiarEstilo('$color')\""; ?> >
De este modo al cargarse la página si ya se ha asignado a una variable de sesión el color correspodente pues se hará el cambio mediante la función. Ahora lo botones que definen que estilo colocar deben tener otra función, una casi igual a cambiarEstilos, solamente que mediante ajax tiene que dar el valor a una variable de sesión. De ese modo cuando se recargue la página o vaya a otra página que tenga el body como lo he mostrado pues se carga la variable del estilo desde la variable de sesión. Obviamente al principio de cada página debe estar la funcion: session_start(). Espero que te sirva lo que te he aconsejado.