If you're going for the cookie option, you can download the jQuery plugin here:
https://github.com/carhartl/jquery-cookie
When someone clicks on one of the links, register the visit:
$('a').click(function () {
$.cookie('the_cookie', 'the_value', { expires: 7 });
});
On the page load, check if they're a returning visitor and work out the new background:
$(function () {
if ($.cookie('the_cookie') == 'the_value')
$('div').css('background-image', 'new image');
});