The expensive pond "soil" is in fact just reddish brown clay. Plain cat litter is also clay. They're similar. The cat litter is much more dusty though. Both require rinsing. I mostly pot my pond plants in dirt that I dig up from our property. It's heavy, clay dirt. I top that with pea gravel. Digging your own dirt is cheapest, then the cat litter, and then the pond "soil." I use some of the clay pond "soil" to pot up some of my smaller pots, mostly when I'm either too lazy to go dig some up, or I'm afraid the pot may be tipped and spilled. When spilt, the clay "soil" makes a lot less mess than real dirt. I doubt there's more leaching from cat litter versus the clay pond "soil."
--------------
These sections on my site may be of some minute help:
http://www.fishpondinfo.com/plants/plant2.htm - pond plant care
http://www.fishpondinfo.com/plants/algae2.htm - pond algae
http://www.fishpondinfo.com/setup.htm#rock - the pros and cons of putting rocks/gravel in the bottom of the pond
---------------
It's up to you if you want to remove the rocks from the bottom of your pond (see my list of pros and cons). Limestone should be avoided in ponds because it will leach over time and raise the pH and hardness. You'll want to check those levels regularly if you have limestone in or around your pond.
The builders put pea gravel in the bottom of my pond but some of the time I wish it weren't there (due to the cons). It does make the shallows look much more natural though. Probably about half of people with ornamental ponds have gravel or rocks on the bottom and half don't.