For the replacement battery you'll need a CR2032 battery with pre-soldered tabs. This is the direct replacement for your old N64 cartridge battery. This is the battery I used and it came with a 3.8mm security screwdriver, which you'll need later.
Unless you have a pulse spot welder laying around, don't solder anything directly to the battery.
As always, Nintendo loves to try and keep us out of their hardware. You'll need a 3.8mm security screwdriver to open the cartridge. Use it to remove the two screws on the back and open the case.
Use a small Phillips screwdriver to remove the electromagnetic shielding.
The battery is located on the same side of the cartridge as the microchips.
My battery is from 1998! That's over 20 years old.
Locate the two large tabs on the other side of the board protruding from the battery. Heat each up with your soldering iron and use your solder sucker to desolder them.
Your replacement battery has one wide tab and one narrow tab. This makes orientation easier as the battery is not reversible. Solder the new battery in place.