You can reach the four Materia Caves after you have bred yourself a Blue, Green, Black and Gold Chocobo through the Chocobo Breeding and Racing side quest. Click on the link below for more information:
The Materia Caves are indicated by red dots on the world map below. More details about how and where to find them are included below:
Can be reached with: Blue, Black or Gold Chocobos
The Quadra Magic Materia Cave can be found just to the northeast of Mideel. You require a Chocobo that can run across shallow waters (which the Blue, Black and Gold can do) in order to reach it.
The reward is a 
Quadra Magic Materia.
Can be reached with: Green, Black or Gold Chocobos
The Mime Materia Cave is located on the east side of the Wutai continent (which is the western-most continent). It is found in an area of the continent that can only be reached by crossing the mountains (which the Green, Black and Gold Chocobo can do).
The reward is a 
Mime Materia.
Can be reached with: Black or Gold Chocobos
The HP <-> MP Materia Cave is located near the entrance to Mount Corel on the opposite side of North Corel). You need to cross a river and a mountainous area in order to reach it (which the Black and Gold Chocobos can do).
The reward is an 
HP <-> MP Materia.
Can be reached with: Gold Chocobo
The Knights of the Round Materia Cave is located on a hidden island called Round Island in the northeast section of the world map. It is not identified on the world map but it is fairly easy to spot once you take your Chocobo out into the ocean. Only the Gold Chocobo can reach this cave.
The reward is the most powerful summon in the game, 
Knights of the Round Materia.
Roundtable Destruction
You will automatically obtain the Roundtable Destruction Trophy once you pick up the Knights of the Round Materia listed above.
