Is ~((A v ~A) v M) a substitution instance of ~(P v Q)?
I am under the impression that it is not, since (A v ~A) is a tautology. This results in ~(True v M), which is always false; whereas in the case of ~(P v Q), there is a possibility of the expression evaluating as True (When P and Q are both False).
However, someone else is telling me that since P is a universal proposition variable, that you can simply replace (A v ~A) with P, which leaves ~(P v M) - a perfectly valid substitution instance.
Which is the case? Can you, or can you not, simply replace a tautology with a variable P?
You can't validly replace a tautology with a propositional variable, no. If you did so, then you could pass from a true formula to a formula which has some instance where it is false. Passing from the true to the false is pretty much the definition of invalidity.
On the other hand ~((A v ~A) v M) is a substitution instance of ~(P v Q). We simply substitute P with (A v ~A) and Q with M in ~(P v Q) to obtain ~((A v ~A) v M). Substitution instances need not have the same truth status as their parent formulas. It uses well-established terminology to say that
~((A v ~A) v (A v ~A)) is a substitution instance of ~(P v Q), even though ~(P v Q) can be true, while ~((A v ~A) v (A v ~A)) is always false. In this way, validity is irrelevant to the question of whether something is or is not a substitution instance of some formula.
Furthermore, the rule of substitution is such that it has to get applied uniformly throughout a well-formed formula. In other words, anytime you substitute one variable V in a well-formed formula F with another (usually longer) well-formed formula S anywhere in the formula, you have to substitute V with S everywhere else in F. It should get noted that F and S need to qualify as well-formed. In other words, they satisfy the (relevant) definition of a well-formed formula. If they are not (they aren't actually formulas then), difficulties can result.
For example of how NOT to do a substitution, consider the tautology (p$\rightarrow$(q$\rightarrow$p)). If we replace the first p with a, and the second with c, then we have (a$\rightarrow$(q$\rightarrow$c)). But, if a is true, q is true, and c is false, then this formula is false, while (p$\rightarrow$(q$\rightarrow$p)) is always true. For a correct example, we would substitute p with a everywhere or p with c everywhere, thus obtaining (a$\rightarrow$(q$\rightarrow$a)) or (c$\rightarrow$(q$\rightarrow$c)).
Substitution often plays a key role in working with tautologies, since anytime you (uniformly) substitute a formula in a tautology T with another formula, the resulting formula T' is also a tautology. This is often part of how axiomatic propositional calculi work, and many axiomatic propositional calculi rely on a rule of substitution. Those that don't often still use notation in their proof analyses which can get read as using a rule of substitution.