I recall finding Moss Stone on one of my single-player maps some time ago... however I haven't seen it recently (after taking a break from MC around Beta 1.2, I've now started playing again on Beta 1.5). I do almost exclusively play on my friends' SMP server now, and so I was wondering if Moss Stone naturally occurs in SMP on Beta 1.5?
Yes, Moss Stone occurs naturally in SMP. It can only be found on dungeons walls. The quantity varies, but my friend got around 55 blocks with only one dungeon, playing in SMP of Beta 1.5. The minimum seems to be 30 blocks, with a maximum of 64 per dungeon.
Dungeon, with part of the floor composed of moss stone:
Source of some information: http://www.minecraftwiki.net/wiki/Moss_Stone