[Disasterpiece]

Simple:

Place a warning box into the template where you like to display it, give it an unique id like id="nojsbox".
Then add a JS function which removes the box:

function has_js() {
var e = document.getElementById("nojsbox");
e.innerHTML = '';
}

Now you just need to call this function.

I'm not the JS guru and can't test it right now, but it should work if you put it into the body onload tag or use jQuery. You'll find the answer via google, but this should point you into the right direction.