The seal was basically the same as saying "this game is licensed by Nintendo." There were some games without the seal, but they were unauthorized and typically Nintendo sued them.
You couldn't get a game on a standard Nintendo cartridge without being licensed, so these games were actually put on reverse-engineered, custom manufactured cartridges[1] that overloaded the piracy detection circuit[2] on the NES.
Interestingly, when Nintendo built the Game Boy, they came up with a novel way of protecting it from unlicensed games: They made the system check that the console had a bitmap of the Nintendo logo at a specific part of the cartridge memory, and refused to boot if it was not there. Unlicensed cartridge manufacturers could then be sued for trademark infringement.[3] This logo was actually the one displayed when the console booted up, which is why if you booted the console without a cartridge inserted, you would see a black rectangle in the place where the Nintendo logo normally appeared.
[1] http://en.wikipedia.org/wiki/Tetris_(Atari)
[2] http://en.wikipedia.org/wiki/10NES
[3] http://fantranslation.org/ja/node/16