So I had the extraordinary good luck to get a shiny Nidorina in Pokemon LeafGreen; unfortunately, I don't have a Moon Stone to evolve it. What's the best way to get one, and how should I go about it?
Well you're in luck. There are a total of 5 in Game.
See this video for more precise locations.
Hope I helped!
Wild clefairy's will always have a chance to carry moon stones, so if you've already used all of them found ingame then go steal some.
Otherwise, there's one in Mt. Moon in the Northwest corner of the first floor (source: Bulbapedia).