A lot of people remove the fish and have at it. I did it fish in, I do weekly WC's and did it over time to make it easier because my tank is so large. I removed about 30% each week and vacuumed the h*ll out of it first to stir up less crud and avoid any ammonia spikes. The 3rd week I picked up my PFS and finished scooping out the gravel. There was a bunch of little gravel pieces all over and thick stuff on the bottom of the tank, was quite gross lol. So I took the siphon part off my handheld vac and just used the tube... It sucked up all the rest of the gravel and crud. Super easy. I then had my prewashed sand and scooped it up and lowered it into my tank and dumped it in close to the bottom. I have a 90 gallon tank, but if yours is smaller it would obviously be a lot less time consuming.
Others remove their fish and put them in a large Rubbermaid tub with filter and heater or airstone, whatnot and go to town on the tank. I didn't want to do that because I didn't want to hassle getting the pictus cats out since I can't use a net for them. My fish didn't seem to be stressed as I was going it. They were intrigued and wouldn't leave me alone during the process lol.