You will need:
An Arduino Duemilanove (other boards will probably work, but you will have to adjust the steps for your device)
Working NES Console
Super Mario Bros. (Note: this must be only the single game, not the two- or three-in-one cartridge)
A controller you can cut the cord from
Two LEDs (two different colors are recommended but not required)
2x ~390 ohm resistors
3x 1.6k ohm resistors
3x 3.3k ohm resistors
4021 (16 pin Shift Register. Note: the 74xx series will not work)
SD Card slot (more on this later)
A pushbutton (not required, but recommended)
A switch (not required, but recommended)
A soldering iron (you'll probably need one)
Arduino Interface, available from http://arduino.cc/
Processing, available from http://processing.org/
FCEUX, available from http://fceux.com/ (you probably want the windows binary unless you know what you're doing)
Step 1: Background information
Every approved submission (called "movies", even though they contain no audio or video data) on their website is simply a series of recorded button presses that in theory can be played back on the actual console for which they are intended. In most cases however the emulator differs too greatly from the actual consoles to make this possible, but in the case of the NES the difference is significantly smaller.
The game choice also makes a big difference as to whether the button presses can be played back or not. If the game relies on any uninitialized memory for randomness, or if it is heavily based on console timing, it may not work. In the case of Super Mario Bros however, as long as the button presses start play back at the right time, the movie will play back correctly.
These button presses are based on frames on the console. Almost every time the console redraws the screen (~60 times a second), the controller is polled for input. However, there are times when the screen is redrawn, but the controller is not polled. These are called lag frames. Due to the difference in the way the emulator handles these lag frames, any movie must be modified to run correctly on the console. This is handled later on.
To turn "in theory" into reality, we will start by modifying the controller.