There are only two secret villages: the Dwarven Town on Grans Island, and the Elven Town in South Parmecia. Neither of these are very difficult to reach.
After you get the Caravan, you travel along the dried up river to reach Creed. As you come off the river, there is the little cave with the sick dwarf. To the left of this is a clump of bushes. One square of this is a lot lighter. This is where the village is:
To the east side of the village is a game-within-the-game. It's basically a battle with one main monster who creates more monsters. Kill the main one and the battle ends. Your time to complete the fight is recorded and added to the list of times. It's tough to beat, but it's good for a laugh. To get there, go clockwise around the outside of the houses and then when you've got the mithril in the bottom-right, follow the 2-hole clearing through to the right and you're there.
There is also a quicker route to get to it, as you can see in this map:
To get into this one, you need the Dry Stone. At one point in the river, north of Galam, there is an odd-looking section, where the river is 'dented' in both sides: use the Dry Stone here.
The dwarves here can use your Mithril (for a fee of 5000G) to make you some fairly impressive weapons!