Assuming we're in $3$-space (so that "the unit normal to a surface" makes sense):
For each point $\gamma(t)$ on the curve, consider $\gamma''(t)$, the curvature of $\gamma$. Since $\gamma$ is a geodesic on $M$, $\gamma''(t)$ must have no component along $M$, so $\gamma''(t)$ is parallel to $n$. But similarly, $\gamma''(t)$ is parallel to $\hat n$, while $n\cdot \hat n=0$. Therefore $\gamma''(t) = 0$ for all values of $t$, so $\gamma$ is a straight line.
In particular, you don't need $M$ and $\hat M$ to intersect perpendicularly, just transversely, for any shared geodesic to be a straight line.