My inclination is to replace the nipples one at a time, working around the wheel, but wait until they're all done to re-true and re-tension. With this approach, I don't see the benefit to de-tensioning all the spokes first.

But having seen Unca Sam's approach, that may be even better. If it ain't broke ...