In order to make mossy cobblestone, you will need cobblestone and a new item, sea goop(not real name)
How to get the Sea Goop Thingy
You would retrieve this sea goop thingy by fishing. If your fishing bobber bounces downwards and does not come up, you know you've got some!
Here's how it might look:(sorry for the humongous green piece of ... ?
http://imageshack.us...0/seagoopz.png/
There is no overpowered part of this, its not like mossy cobblestone is different than cool looking cobble.
You also need a fishing rod as well.
Don't Forget to Read This Part
If this annoys people since mossy cobble "should be a rare novelty item" then it can be a different tint of green, or this mossy cobblestone will be green, but normal dungeon mossy cobblestone should have red "veins" of color going through the rock instead.
Here's a possible texture:

Uploaded with ImageShack.us
This could also work for stone bricks btw...
Another use for the sea goop thingy is that you can place it like a block, when placed on a shoreline, it will attract squids. This can be useful for capturing squids, or getting lots of xp.
I would change the title to "Sea Goop Thingy" if I could.
















