Hi JJ,
I'm prolly one of those who complained about not being told everything needs JS-- as a non-JSer I always appreciate being let known that hey, this site uses JS for stuff (and often it's also nice to know what for, because one of the reasons I specifically keep it off is to avoid MooToolsy drag-n-drop fading blitzkrieg Nintendo-generation short-attention-span superfeatures and that sort of thing). Knowing scripting is used for "this" "that" etc I think is always thoughtful for a web dev to do, as there's nothing more frustrating that not figuring out why something doesn't work, when it's because your browser isn't supporting applets/cookies/java/scripts/css/other things you can never guarantee a user agent can or does support. Of course, the goal is to have the user never notice, have pages built with progressive enhancement, but when that's not possible, a small message is nice.
That said, it shouldn't have to take up a huge amount of space on the page or anything. Most sites get away with a small message at the top of the screen. Without cookies I don't see how people could have a "don't show me this again" option so, maybe the box could be moved somewhere else, but otherwise, I find it more valuable on-page even if some find it annoying.