Only load the background-image when it has been fully loaded?

You can't do it when JS is disabled. However, what you can do is set the background image in CSS and then use the following script (assuming the element has the ID myelem).

(function() {
    var elm = document.getElementById('myelem'),
        url = 'background image URL here';
    elm.style.backgroundImage = "none";
    var tmp = new Image();
    tmp.onload = function() {
       elm.style.backgroundImage = "url('"+url+"')";
       // or insert some other special effect code here.
    };
    tmp.src = url;
})();

EDIT: Although, make sure your background images are optimal. If they are PNG, try having them Indexed with as small a colour table as possible, or make sure the alpha channel is removed if there is no transparency. If they are JPEG, try adjusting the compression.

If the image is included with an img element:

<img src="bg.jpg" id="img" onload="this.style.opacity='1'">

<script>
    document.getElementById("img").style.opacity="0";
</script>

That should load the image normally if JavaScript is disabled, but show it only once it loads assuming it's enabled.

One thing to note (that I overlooked): some browsers will not even attempt to load an image if its display property is none. That's why this method uses the opacity attribute.