A common technique to save scores/settings in games is to replace the batteries while the game is on. I'm not sure how much is saved to nvram on a new Stern. I wonder though, if the battery hasn't failed yet, why are you replacing it?

Good call. if you're comfortable with a dmm, you can take a voltage reading from the battery. If it is less than 3 volts, replace it. If not comfortable with the dmm, just replace it with the game on, and it'll be fine.

Replacing is a common practice with AA alkalines, but newer Sterns typically use a flat lithium-ion battery, they last for years with little risk of leakage when they get old. No real reason to replace it until it dies.