I've heard that some operating systems don't actually allocate malloc'ed memory until the program tries to use it. Is this legal?

It's hard to say. The Standard doesn't say that systems can act this way, but it doesn't explicitly say that they can't, either. (Such a ``deferred failure'' implementation would not seem to conform to the implied requirements of the Standard.)
The conspicuous problem is that, by the time the program gets around to trying to use the memory, there might not be any. The program in this case must typically be killed by the operating system, since the semantics of C provide no recourse. (Obviously, malloc is supposed to return a null pointer if there's no memory, so that the program--as long as it checks malloc's return value at all--never tries to use more memory than is available.)
Systems that do this ``lazy allocation'' usually provide extra signals indicating that memory is dangerously low, but portable or naïve programs won't catch them. Some systems that do lazy allocation also provide a way to turn it off (reverting to traditional malloc semantics), on a per-process or per-user basis, but the details vary from system to system.