No matter how many caves I look in at any y level I can never find any soulstone. Am I doing anything wrong? Does it spawn like ancient debris where you have to strip mine for it or something?

It should spawn like a regular ore, try making a new world and flying around in spectator for a little.
It should be very common, iron-like, however I've seen reports of many features being weirdly rare in malum.