I am asking this because NES ROMs were usually some kilobytes
The NES Cartridge for Super Mario Bros. is actually 40 KB, easily enough space for a bit of demo.
Question is, how was the example play stored in the game data?
A disassembled version is easy to google, here is the section that performs the demo:
8340: 01 80 02 81+ DemoActionData .bulk $01,$80,$02,$81,$41,$80,$01,$42,$c2,$02,$80,$41,$c1,$41,$c1,$01
+ $c1,$01,$02,$80,$00
8355: 9b 10 18 05+ DemoTimingData .bulk $9b,$10,$18,$05,$2c,$20,$24,$15,$5a,$10,$20,$28,$30,$20,$10,$80
+ $20,$30,$30,$01,$ff,$00
836b: ae 17 07 DemoEngine ldx DemoAction ;load current demo action
836e: ad 18 07 lda DemoActionTimer ;load current action timer
8371: d0 0d bne DoAction ;if timer still counting down, skip
8373: e8 inx
8374: ee 17 07 inc DemoAction ;if expired, increment action, X, and
8377: 38 sec ; set carry by default for demo over
8378: bd 54 83 lda DemoTimingData-1,x ;get next timer
837b: 8d 18 07 sta DemoActionTimer ;store as current timer
837e: f0 0a beq DemoOver ;if timer already at zero, skip
8380: bd 3f 83 DoAction lda DemoActionData-1,x ;get and perform action (current or next)
8383: 8d fc 06 sta SavedJoypad1Bits
8386: ce 18 07 dec DemoActionTimer ;decrement action timer
8389: 18 clc ;clear carry if demo still going
838a: 60 DemoOver rts
As you can see, it's a replay, two bytes per action, one byte for the joypad bits, one byte for the delay until the next action (timing).