I just ran headlong into this problem yesterday -- the user was very upset and was unaware that he had Javascript disabled (thanks to IE's convoluted security settings).
My kludgy solution is to put the following HTML in the checkout instructions (admin/store/settings/checkout/edit/messages):
<noscript>
<p style="color:red">You appear to have Javascript disabled. This page requires Javascript. Please <a href="http://support.microsoft.com/gp/howtoscript" target="_blank">enable Javascript</a> and reload this page before continuing.</p>
</noscript>