How can I set a persistent template variable to use across multiple pages in one site visit?
Sounds like you need a good cookie solution to keep track of which background has been chosen for each visitor.

I'd recommend using the LJ Cookies plugin to easily set &amp; retrieve the filename of the background image.

(I don't believe the cache tag will be useful to you in this case.)