It depends. You can get what's called a thread chaser or thread repair tap and try running that through the threads first. If they aren't too far gone it might clean them up enough to function again. Do not use a regular tap, it will cut more metal away than you want for an existing threaded hole.
Drilling out/tapping and using an insert like a helicoil might work. I've had hit and miss luck with those holding well. It really depends on the location and forces on the bolt/nut. Chances are pretty good that it will work in this case as most of the force is shear across the bolt vs trying to pull the nut out.
Whatever you do use a liberal amount of anti-seize when you put it back together. These tend to rust pretty badly.