I was wondering if maybe they preconverted the videos into a sequence of tilemaps and a set of approximate tiles. I notice they are only using the same 5 colors, which is under-utilizing the capabilites of the nes which should be able to display a 13 colors at the same time. (Each individual tile uses one palette of 4 colors, and there can be max of 4 palette used at a time, but one background color is shared by all palettes.) To more fully utilize the nes they could also use a different set of 4 palettes for every frame, which would allow for a much broader range of colors.
Hypothetically, the NES could play streaming video. For memeory limitations, a custom rom cartridge could be used which would grab a new set of video frames (consisting of tilemaps + tilepatterns) via a network controller. The 6502 core does not need to decode video, but could simply swap in chunks of these tilemaps+tilepatterns which the picture processing unit displays.