Listen closely in caves and underground places with headphones. When you hear what sounds like a bunch of the same monsters going nuts, you may be near a dungeon. You can tell its direction in the L and R ears by turning around, though you can't tell above or below too well. Just dig around and find the source of the noise.
If you found a dungeon but it has no mossy cobblestone in it then either you are in multiplayer and someone nicked it or you were not in a dungeon (could you be referring to temples or mineshafts?). A dungeon is a small, underground room with a spawner that you can deactivate by lighting the room up with torches (and sticking a torch on top of a spawner, I believe). The floor of a dungeon is made of mossy cobblestone. Best way to find them is to either run along cave systems listening for mob noises or, if you are into cheating, to make a transparent texture pack (might not be allowed in multiplayer!).
Also, I think that you had to have the ''Generate structures'' option ON while creating that world for them to occur, but don't take my word for it.
As 1.2.5 there is only two blocks with moss in the game. Mossy cobblestone and stone bricks with moss. Mossy cobblestone is found in dungeons,the little underground rooms that contain a chest with whatever crap somebody left in it and a mob spawner put there by some black magic. Mossy stone bricks however are found in strongholds,the massive messy confusing castle that got buried by black magic too(they also contain enderportal). To find dungeons,just go in caves,explore a lot of them and listen to the scary noise. For strongholds you need to mix blaze powder and ender pearl. Throw it,just follow the direction and don't forget to bring more then one and pick them up when they fall. When they start going into the ground,dig deep down,your stronghold is there and i have no idea to navigate through them.
I discovered a good way of finding strongholds.
1-Press F3 and find your map seed and write it down
2-Start a creation game with that same map seed
3-Use the unlimited Eye of Ender to throw in the air and lead you to a Stronghold location
4-Dig straight down until you find said Stronghold
5-Press F3 and write down the x,y,z coordinates of the Stronghold
6-Go back to your original game and follow those coordinates to Stronghold
Either mossy cobblestone or mossy stone would work, I've looking all over in dungeons but have never once seen any and I have never found a stronghold - where are they ?
Mossy cobblestone is officially named as moss stone (cobblestone texture with green moss). You can found it in every dungeon that has a floor. So if you are looking this you have found it, because you claim to have looked all over in dungeons.
Mossy stone bricks are a variant of Stone bricks (stone brick texture, with green moss) that can be found in strongholds.
I'm gonna go with EvilSean's idea of copying the seed on a creative mode to find a stronghold, but have to strongly disagree with a dungeon being a spawner room. I have 3 spawner rooms I've found (oddly all within about 20 blocks of each other so I connected them all with a hallway and glass to keep the spiders at bay) and none of them had mossy stone anywhere around them. Now a dungeon MAY have mossy stones in them but it's not 100% obviously Not trying to start anything, just want to clear up any confusion that moss is always by a spawner.