In the method of Lagrange Multipliers we want to maximize $f(x,y)$ constrained to a level curve, i.e $g(x,y) = 0$. To do so we define the Lagrangian function $$L(x,y) = f(x,y) + \lambda g(x,y)$$ It makes sense that the critical points of $L$ are when $\nabla f = -\lambda \nabla g$.
Here is my question: Why does this critical point have to be on the constraint?
You are missing the second condition of Lagrange optimality: that the derivative of the Lagrangian w.r.t. $\lambda$ has to be equal to zero! $$ \frac{\partial L}{\partial \lambda} = 0$$ This condition implies that, at optimality, $g(x,y)=0$.