The locations on the world map should be immediately accessible, but not all are available right from the start of the game. You should be able to find the first one just northeast of Houton on the world map, for instance, but some of the others you'll need to play longer into the game to find.
The four maps and what they unlock are listed below:
- Ratty Old Map: Unlocks Cairn of Ardagh
- Ancient Parchment: Unlocks Cairn of Carrowmore
- Weather Stained Map: Unlocks Ruins of Emain Macha
- Blood Stained Map: Unlocks Ruins of Tara