From the documentation:
Evaluate[expr]
causes expr to be evaluated even if it appears as the argument of a function whose attributes specify that it should be held unevaluated.
So, let's walk through your examples (with symbols that are easier for me to type):
Case 1
Given
p = g^2;
We start with
With[{g = 3}, {p, Evaluate[p]}]
(* The Evaluate appears as an argument to List which is itself inside of With. Any
Evaluate that is a direct argument of With would evaluate, but in this case there is no
such situation, so With just does its thing. Next, the With construct does *lexical*
replacements, so it looks for instances of literal "g" symbols, finds none and so
just evaluates the body to get... *)
{p, p}
(* Now the evaluation engine continues the evaluation, finds the definition
for p and evaluates to... *)
{g^2, g^2}
(* If it finds no other definitions to apply, it'll just stop there. *)
Case 2
With[{g = 3}, Evaluate[p]]
(* In this case, Evaluate is an argument of With, which has the HoldAll attribute,
so Evaluate interrupts the normal evaluation order and forces itself to
evaluate first... *)
With[{g = 3}, g^2]
(* Next comes the lexical replacement... *)
3^2
(* ...and finally... *)
9