You will need a special screwdriver to access the inside of an NES cartridge. Using a 3.8mm NES security bit, unscrew the screws holding the cartridge together. There will be 3 total.
The board is resting inside of the cartridge shell—there are no tabs to hold it in place. Remove the board by lifting it from the shell.
Flip the board over so the battery is facing down. Using a soldering iron, melt the existing solder that holds the battery in place. Suck up the additional solder with a solder sucker. When enough solder is removed, the battery can be wiggled loose.
You need this CR2032 battery with pre-soldered tabs to replace the old battery.
Put the new battery into place on the board. Be sure to have the positive and negative ends line up. You can use the pictures in this guide for reference.
I'm using a leftover CR2025 from replacing a Game Boy cartridge battery; it will work, except the tabs are slightly different and thus need to be clipped. Be sure to pick up a CR2032.
Solder the new battery into place. I always use a little bit of flux when making new connections.
Put the board back inside the shell and screw the cartridge together. You will need the 3.8mm NES security bit to close the cartridge. There are three screws used during this step.
It's time to boot up the NES and play some Tecmo Super Bowl (or whatever game you have)!
Play enough to warrant a save on the cartridge. The goal here is to create new save data. Once you've created a new save file, reboot the NES and load the same save data. Congratulations! You've given new life to your old NES game.