A wild Cleffa, Clefairy, Clefable and Lunatone all have a 5% chance of holding a Moon Stone when they appear.
Cleffa and Clefairy can be found at Mt. Coronet etc.
Lunatone can be found at Spring Path, Lake Verity
Acuity etc. You need to have Sapphire inserted into the GBA slot to find a Lunatone
hope I helped! :)