En la página que pusiste como ejemplo, efectivamente se hace con Javascript, se guarda en una cookie el fondo elegido por el usuario y al cargar cada página se recupera ese valor, en varios temas ya se trató como guardar cookies (por ejemplo, uno reciente:
http://www.forosdelweb.com/f13/guard...ookies-645484/).