There are some PLC's out there that you must power down in order to change the battery, some SLC's for example. In those cases, have the new battery ready and unpacked (and in your hand), kill power, pull CPU, and make the change fast.
Ones that require power down usually have a capacitor backup that will last for 1 to 3 minutes, and are usually identified by having the battery located in such a place as to require removal of a module from the backplane to change it.
In most cases though, leave power turned on to change the battery. Just like the alarm clock at home.