I've gotten 8 so far. It seems to be on about the same rarity as getting a particular gem or blackrock (8 dark sapphires - 8 small pieces of blackrock - 8 niter deposits). On average, that seems to be about 300 strikes for me (human, GM mining, 0 luck, regular shovels set to ore).
You get a message when you mine one up and the deposit appears on the ground next to you. I didn't think to write down exactly what the message said, but it's something like - "You have mined up a <small, large, huge, massive> deposit of niter. You can mine it to obtain saltpeter."
I've gotten massive and huge so far. As you mine it, it decays to the small size. Maybe it does this over time also? Huge seems to be in the 50-60 range total; massive seems to be 60-100. On any strike you can get 0-4 saltpeter.
I've gotten them in both the Trammel and Felucca classic dungeons - seems to be near the same rate, but I don't really have a large enough sample size to say for sure.