What is the best way to tell anonymous users apart?
Session variables seem to be the way to go


Don't forget that session variables rely on cookies


  Have I missed any options?



The traditional solution would be to use the ip address as a fallback if cookies are disabled.
PHP does support an alternative to cookie-based sessions -- it can rewrite the URLs to include "?PHPSESSID=xyz". However, securing this can be difficult.
Another approach would be to use html5 local storage and do all the cusomizations on the client-side. This will work in all modern browsers regardless of cookie or firewall settings.