You have to ride a black Chocobo to access Lodestone Cavern. Black Chocobo lives in a Chocobo Village up north.

*** Make sure that you equip non-metallic weapons and armors before entering Lodestone Cavern. 

Boss: Dark Elf
You cannot defeat him in the first fight, so don't bother healing your party. After Edward playing a song through a phone (Whisperweed) he gave to Cecil, you can now defeat him. First use Silence and then auto attack.