How does an anode metal come into solution if it cannot react with an electrolyte?
I was just wondering then that when you have a galvanic cell which has a $\ce{Mg}$ metal anode submerged in sodium chloride solution, how the magnesium metal gives two of its electrons and come into solution (as magnesium ion) even though it does not react with (and cannot react with) sodium chloride?


Your misunderstanding stems from assuming that the electrode reaction has to be the same sort of single-displacement redox reaction that would occur with no electrodes present at all.

At a dissolving magnesium anode$^\dagger$, the only reaction that needs to occur is the one you wrote involving magnesium:

$$
\ce{Mg\!(s) -&gt; Mg^2+\!(aq) + 2e-}
$$

The potential applied to the electrode pair is what enables the above reaction to occur without a paired reduction reaction at the anode surface.  Instead of being taken up in another chemical reaction, the electrons are drawn into the anode and on into the connected electrical circuit. Those electrons are then "pushed" into the cathodic reaction, whatever it might be.


  From what I understand, anode material is chosen so that it does not react with the anode electrolyte solution.


This is true, but does not have to strictly hold. MaxW is right: $\ce{Mg}$ does react directly with water. But, the reaction is slow enough that it's perfectly safe, and that one can conduct useful electrochemical operations even while it's going on (e.g., see here and here).


  Is it that the metal is more stable in its ion state and thus readily gives up its electrons?


Despite what one reads from a table of standard reduction potentials or a metal reactivity series, in practical electrochemistry, the above is true for most metals, except for the noblest of the activity series. In my experience, it's usually a lot easier to dissolve metals than to electrodeposit them.  You may have to use additional chemistry to make it happen (e.g., including $\ce{HF}$$^\ddagger$ to strip the passivating oxide from $\ce{Ti}$, $\ce{Nb}$, $\ce{Ta}$, etc.), but once the metals are oxidized/dissolved they tend to stay that way.



 $^\dagger$ Operating at $100\%$ faradaic efficiency. Other reactions that might occur in this system, depending on the applied potential, include the chloride oxidation reaction you noted and water electrolysis to oxygen gas.
 $^\ddagger$ $\ce{HF}$ is very dangerous, do not use at home!