Hi, generally speaking, putting soil in a pond is not a good idea, even gravel will prevent you from giving the occasional good clean out, and even without fish this will become necessary. (Even in a wildlife pond, I would recommend that you do keep a dozen or so small fish, minnows are ideal, just to keep down the inevitable mosquito larvae.)
The first thing you must do is get yourself a water test kit. I have recently built a 10.000 gallon wildlife pond, and my plants, which by now should cover 2/3 of the pond area, and the essential oxygenators should be prolifically occupying the lower levels, are all stunted, & just surviving. Why? Because the water, as supplied by my utilities company, has a ph of less than 6.0 and a hardness of basicly zilch!
The water companies are allowed to supply water down to a ph of 5.5, and in this, plants just don't grow!
I have managed, at long last, to source a bulk supply of bicarbonate of soda, but it was a long search!
You may not have this problem, but it is best to check!
The most important plants are the Oxygenators, and probably Canadian Pond Weed is the most readilly available, cheapest, easiest to grow, and is most prolific!
YOu should get a couple of water lilies, because their large leaves give a good surface cover, but not if you are going to install a fountain - they will not tolerate moving or splashing water.
This subject is so big, and it is so late, that I will sign off for now, but I will try to find a couple of good plant supplier links & post these.
Jeremy