BB are all over the tank, but most will not be in the substrate. Regardless, the BB will repopulate over time, so any large changes in the decor (like substrate) can be addressed by simply lowering feeding amounts and then increasing food amounts gradually over a period of time (like a week.)
There is not one best way to do this. Some recommend removing fish, then doing the change, especially if the change can be done quickly. Others will do it more slowly and carefully while the fish are still in the tank, using a scooper. If the tank can be divided with a temporary wall (like egg crate), the second method seems pretty good. Since some fish are biters, jumpers or skittish, while others aren't, it's hard to say which way is better.
If you have large rocks/driftwood and the substrate hasn't been worked for quite a while, there will be a risk of toxic gases when move these. That might be a reason to remove the fish. Most people don't have this issue, but deep substrates that have not been moved or have been covered for a long time have a real risk.
Moving the substrate will cloud the water, and if it's sand, send dangerous particles to the filter, so it's best to turn off the filter during the process or cover the intake with a sponge. You can turn the filter on periodically to keep the water from going stale if the change takes a while. For sand, I'd certainly leave the sponge in place with the filter on until the substrates has settled.
