It's also often used to mean "not material," or "not obeying the same laws as most stuff we see." So the stuff we see around us is the "natural," and things that don't follow natural law are "supernatural."

I think this is the key. Supernatural phenomena can't be defined to obey natural laws; if they did, they would be blatantly impossible. (For a really detailed example of this, see Sean Carroll's blog post Telekinesis and Quantum Field Theory.)