Moonstone Ore is obtained from meteors which rarely fall during the night time near a player whose magic level is high enough (default: 10). These meteors have a very rare chance of spawning, and will fall within approximately 32 blocks of the player, and only on the cover block of the player's biome - grass for plains, sand for desert, etc. The meteor consists of a small amount of Moonstone Ore and stone.
Mining a piece of Moonstone Ore will result in a piece of Moonstone. This amount is affected the Fortune modifier on pickaxes, meaning that you will gain more Moonstone by using a pickaxe enchanted with Fortune.