well, I had the exact same situation, somewhere on my land was very wet, and trees had a hard time growing there, they wher all small with roting parts, so I cut everything in that area, leaving the trees that where on mounds, because they looked healty, and I wanted to keep some shade on the pond.
On the first year, I scraped the top soil, putting it aside, uprooted all of the stumps, and slowly began to dig what would roughly look like a "T" shaped pond. I only dug a shallow part of the pond so it was not at its final depth. Of course this was done using an excavator.
I did not work on it on the second year, however, life was very quick to take home there. There where thousands of tadpoles in my unfinished pond.
On the third year, I completed the work, taking extra care not to kill my new buddies (the frogs and tadpole did an insane difference in reducing mosquitoes and flies in the immediate area of the pond) So now it is about a tenth of an acre and roughly 10 feet deep in the middle with many terraces at varying height. I added a lot of debris, mostly stumps and stones to create more habitat for wildlife.
So far I havent added fish, I probably will, but I want to leave my pond naturalise for at least two more years so that there is enough biodiversity for me not to have to feed the fish.
Im am also planning on planting edible water loving plants like duck potatoes and lotus, I already have the seeds, but we still have 4 + feet of snow in the woods so, that will wait.