Hard to put a figure on it, but for me on an average I might see one every 4-5hrs of exploring. Might see 10-20 Water Worlds before getting one. Saying that, it seems to be a little area specific. By this I mean some areas seem to have more than others, and some sectors seem to be completely absent of them. Last week I came across 3 in a matter of an hour or so, but that is the exception from my experience.
I might have found 10-15 in about 1500 systems visited this trip.
What seems to be rarer for me is the Water Giants, I have only just found one after 1800 systems visited!
Keep hunting! You will find them!