Same here! I'm a new player and I spent DAYS of in-game time looking for clay. Travelled around 1000 tiles in each direction. Looked near water. In plains. In mountains. Near lakes and near the sea. By eyes or randomly starting at the ground and seeing what type of tile comes up. Found lots of different rock, sand, different soil types, peat, various minerals, etc.
Still cannot find any clay anywhere
Oh and there's rain and there's various types of reeds in the water, so based on what I've read so far - clay should be there.
I have to say that this is pretty frustrating - it goes from "hardcore game" category into "frustrating" category, especially when I have an hour or so after work to play only.