What you're talking about is called "ROM hacking."
Now you'll want to be careful here because there are serious legal issues (note, I am not a lawyer): For one, to hack a game, you need to find a ROM image of the game you're trying to hack. There are sites that provide downloads for these, but I will not link to one. You're on your own here. The other issue is that a hacked game would count as an infringing derivative work. In practice, however, the game companies mostly ignore the ROM hacking scene.
Legal issues aside, these are the essentials for ROM hacking:
- A ROM image of the game you want to hack (see the warning above).
- An emulator. In theory you could write your hack to a cartridge and play it on an NES, but that assumes you still have an NES, so emulators are the next best thing. Note that emulators are perfectly legal (it's the ROMs that aren't); for NES ROM hacking and homebrew development, I would recommend FCEUX. It has a built-in memory viewer and an excellent debugger.
- A hex editor. I recommend HexEdit. As of now, it's freeware. Sorry, it's for Windows only.
- A tile editor, for editing graphics. I recommend YY-CHR. Again, it's Windows only.
Romhacking.net hosts other useful tools as well.