two perpendicular vectors to one vector would be parallel?

Assuming that the set $S$ is the collection of points determined by the constraint $g(x)=c$ and $c$ is a regular value of $g$, then it has codimension $1$. That means $S$ would be a curve in the plane, or a surface in three dimensional space, etc.

Thus the tangent space of $S$ at each point is $n-1$ dimensional and one may obtain tangent vectors at a point $\bf{r}_0\in S$ as the derivative of a curve passing through this point. The argument shows that for any curve (and correspondingly any tangent vector $\bf{r}'$) you will have that $\nabla f$ and $\nabla g$ are both orthogonal to $\bf{r}'$. Since they are both orthogonal to the same $n-1$ dimensional subspace of $\mathbb{R}^n$ they must lie in that last remaining dimension and hence be parallel.