How do you explain that in $y=x^2$, y is proportional to the square of x? My understanding is that all proportional relationships are linear relationships. If this is indeed the case, how is it that we can also say that in a non linear equation like $y = x^2$, y is proportional to $x^2$?

The definition of proportionality is that $A \propto B \iff A = kB$. So A is linearly related to B, and also $A=0$ iff $B=0$.
In your case, $y = (1) x^2$ so y is actually proportional to $x^2$.
I think you are confused by "y is linear to x squared". Actually linear means that the power is 1. But when I say that y is linear to $x^2$ it means that if you take $x^2$ as one variable, lets call it $z$, then $y = z$ which is linear.
Linear also means that the graph is a straight line. If you draw a graph between y and x it is not a straight line. So  y is not linearly related to x. But if you make the x axis as $x^2$ it will become a straight line. Then we can say y is linearly related to to $x^2$.
Clarification for the graph:
Suppose we graph y = x^2. The result is a parabola.

But if you plot y on one axis and (x^2) on another axis, that means you dont plot y = x^2, but you treat x^2 as a single variable and you plot it along an axis, you then will get a straight line.

Here I have let x go from 1 to 5. On the horizontal axis, I have plotted the numbers $x^2$, i.e. $(1,4,9,16,25)$ and on the verticla axis, I have $y=x^2$, i.e. $(1,4,9,16,25)$.
