Well, if i'd have to do something like that, then this is how i would do it:
1) i would create a directory for themes.
1.1) i'd put all themes (templates, images, CSS, &#106avascript) into a subdir of this themes directory.
1.2) i'd create a config script inside themes directory (this is where i would put all the names and id numbers of all themes).
2) I would organize my themes so that all of them has required configuration script.
3) When user loads some page, i'd check for cookie
3.1) no cookie or cookie is not valid => i load default theme (found in theme config - 1.2).
3.2) cookie is valid => i load theme whos id is in the cookie.
4) When user clicks on a theme link (he wants to change it), i'd check if it's valid.
4.1) New id is not valid => leave it as it is now.
4.2) New id is valid => store the new id in the cookie, load the page using the new theme.

I'm not sure what else is needed here. Well, it might be harder if you're not using template engine (like smarty), but it shouldn't be very hard.

Smarty is very powerful and fast PHP template engine writen in PHP.
I don't know of any easy to understand tutorials or explanations. But most of the Content Management Systems and forums has this, so you could find some open source projects and look at it.