How does a gene "know" what to change to?
Using your example, the gene doesn't know anything. Mutations cause some of the offspring of the red frog to turn green, some to turn blue, some to turn fluorescent yellow, and some stay red. Birds can't see the green ones as well as the others, so more green frogs survive and make more green frogs. The red frogs, the fluorescent yellow ones, the blue ones, mostly get eaten. After a few generations, almost all the frogs are green -- not because the gene knew anything, not because the mutations went in any direction, but because all the other changes were counterproductive and got eaten.

The gene doesn't know anything. It's just a bunch of chemicals that randomly react with cosmic rays, chance, whatever. Most of the changes are irrelevant or actively bad, and the frog that's carrying those particular chemicals doesn't survive. But sometimes the change benefits the frog carrying the particular chemicals and then the frog sends those chemicals down to its progeny.

Obviously this is hugely over-simplified. A short and simple intro to the basics of evolution is Understanding Evolution, by UC Berkeley.