Use a big net to get anything at the bottom of the pond, then drain the water -- a Python will actually work, but you can bale with buckets, use a wet/dry vacuum, or pump the water out with a pump.... Get as much debris off the bottom, INCLUDING ANY MUCK OR MULM (black, dark, stinky, muddy stuff). Removing the mulm is of the utmost importance as it harbors the most nasty stuff.... Do not scrape the algae off the sides and do not leave the pond empty as the algae will die off.
Refill the pond, add dechlor and throw in several bunches of submerged plants like anacharis from the local fish shop. You can rubberband the anacharis around a rock and toss it in the pond.... or plant it in a bucket or pot in aquarium gravel.... The submersed plants provide a safe place for the fish and they will feel much more secure with it in the pond. It will also do a lot to balance the water, lower nitrates, provide vegetative matter for the fish to feed on, provide safe harbor from predators, and harbor fry after a spawn. Buy several bunches, and be ready to trim it once summer comes..... It can grow an inch a day in the heat, but don't let that deter you. Get it -- the fish need it.
Okay, once the water is in the pond, wait a day to let the water temp stabilize. I recommend that you hold off putting fish in the pond until water temps get above 65 degrees consistenetly. The fish will do much better in warmer water in the late spring than starting them off in the middle of winter, if it's cold in your area. Fish need to be conditioned with lots of rich protein food to get through a winter without much food, so hold off.
BTW, in answer to an earlier question about beneficial bacteria, the bacteria needs something to feed off of. Taking the fish out of the pond lessened the ammonia, but if there's rotting bugs and vegetation in there then there's bacteria. Doing a 100 percent water change will not harm the bacteria, but do not allow the pond to completely dry out. Do not leave in the middle of the job. Try to get it done in one day.
Also, have a covered bucket nearby to put any frogs in. Winter ponds have frogs usually, so be prepared for them. Since it's cold, they may be sluggish. Once the pond is filled and the water is a good temp you can put them back in. Don't forget the dechlor!
After the pond is filled, it will be time to turn on the pump and try to see if you can get the water to recirculate.... FIRST, WITH THE PUMP UNPLUGGED, CHECK THE ENTIRE LENGTH OF THE CORD FOR ANY CHEWED SPOTS OR RAW WIRE STICKING OUT!!!!! If the cord is damaged, get another pump. Do not try to work with a damaged electrical cord. Squirrels and other rodents LOVE to chew on cords, so check it carefully if it's been outdoors for awhile. I check mine twice a year when we are changing over components on the pond (winter to spring, and fall to winter).
If the pump has been in that mucky pond, you should take it out, take it apart and clean the impeller and magnet. Awful slime and junk can clog a pump and interfere with an impeller and impede the function of the pump. A good thorough cleaning is usually all it takes to get a pump back up and running.
If you have a filter, hook it up to the pump and then turn on the system.... Even an airstone on a smallish air pump will begin to move the water if you do not have a pump ready. Circulating water is important as it will not sit and stagnate. Check the waterfall to be sure water is flowing over the rock and not leaking from the pond. A spray from a waterfall can quickly empty a pond, so watch to be sure the water is going where it is supposed to go. Check for the rate of the water at the fall. If it's flowing too fast you may be able to adjust the pump.
If you can, add some marginal plants at the side of the pond in a bucket in the water. Japanese water iris or pickeral weed is very pretty and will not grow out of hand quickly, like some others. Goldfish LOVE marginal plants. During mating season they will chase each other through the reeds and spawn. It's really something to witness. Also, if you can, invest in a dwarf water lily. Plant it in a bucket and put it in the middle of the pond. The water lily pads will shelter the fish and when they cover more than half of the pond surface any green water or excessive algae will go away. Water plants are a very good thing in any goldfish pond. If you need ideas on how to plant the marginals and water lilies, post a separate thread and I'll tell you how. It's totally easy -- messy, but easy, LOL...
Okay, once the water is above 65 degrees and you're sure your pump is functioning and the filter is filtering (it will filter debris even with no fish in the pond, so rinse the media regularly), you'll be ready to add fish. I would start off slow. I added SIX very small feeder goldfish to a 2000 gallon pond when I started.... So for your small pond, you may want to add two fish and see how things go. I'd still like to know how many gallons your pond is.... Do not overstock the pond. Try for one fish for every 40 gallons.... So if you've got an 80 gallon pond, you'll stock two fish, tops.... Remember goldfish breed like rabbits, so understock..... After a few years my six original fish numbered at more than a hundred!
Finally, if you're concerned about predation, cover the pond.... I check my pond at least twice a day in warm weather -- once a day in winter. And in the summer I'm usually out there working in the garden a lot too.... You should check the condition of the fish, keep an eye on the water level and top off if necessary, do water changes (DECHLOR!) trim plants. feed fish, and rinse filter media when needed..... And don't forget to take time out to just sit and stare at the fish! It's so relaxing and wonderful! Nothing is like a pond, really..... It's the one thing in my garden that is really worth all the work.