Summary:

It's low resolution at only 256 x 80, stretched vertically to the screen size.

It's only 16 colors so only 4 bits/pixel.

That comes to 10kb per frame.

A variant of Huffman coding gets it to 3.52kb per frame.

It's at 15 fps and is 12.5 seconds in length.

15 x 12.5 x 3.52kb = 660kb, which fits in a 4mb cartridge.

There is dithering to give the appearance of more colors, and it's done in vertical stripes rather than checkerboards because that compresses better. Then at runtime, every other scanline is offset by 1 pixel, and in opposite directions every other frame, so the dithering blurs back together to give the appearance of many more colors.