James, Michael has it right in all counts. If you actually took a densitometer and measured the reflection densities of my prints you will see that those areas that are "pure" black have no more than 1.3 RD. And the dark areas with texture only have about 1.1 to 1 RD. The trick is to use what Arentz calls "a convincing black," that is you calibrate your material so maximum black is only 90% of the black possible by the paper. This gives the "illusion" of having very deep rich blacks when, if compared to a silver print, they tones are actually not that black.
I use Socorro paper, and somewhere in this forum you will find a thread where I am bitchin and moaning about this paper. Thanks to Clay's advice of doing a presoak in 2% Oxalic acid I was able to control this paper and get consistent result. But as you state the paper is also very important in the final outcome, I use Socorro because it is the easiest paper for me to get that is not too expensive and has high quality, but from what I understand most people beleive COT 320 and Arches Platine are the papers of choice for printing in pt/pd.
In the beguinning you will have to search for a paper that "fits" your printing style, once you find it stick with it and get it to wrok for you. The temptation to try many different papers is great but my experience as a beguinner is that is best to stay with one paper and learn all you can changing as few variables as possible. Some might disagree with me, but I would say stay away from Cranes Platinotype, somehow it is the paper B&S recommends to people just getting started but I found this paper lacked "punch" and the prints although ok always lacked something that is hard to pinpoint but definitly not there.