Circular geodesics
You can see geometrically that the normal at the surface at the point $\sigma(s,\theta)$ is the vector $N_\sigma(s,\theta) = n(s)\cos \theta + b(s)\sin \theta$. If $\alpha(\theta) = \sigma(s_0,\theta)$, then you can check that $\alpha$ is parametrized by arc-length, so it suffices to check that $\alpha''(\theta)$ is parallel to $N_\sigma(s_0,\theta)$ and you're done.
Hint: In general, if $\sigma'\times\left(\sigma'\times\sigma''\right)$ is perpendicular to the surface, then $\sigma$ is a geodesic. However, for a constant speed curve, we only need that $\sigma''$ is perpendicular to the surface since $$ a\times(a\times b)=\frac{b\cdot a}{a\cdot a}\,a-b $$ and $\sigma'\cdot\sigma''=0$ for a constant speed curve.
From Comments: Two surface tangents are $$ \partial_s\sigma=t+a(\cos(\theta)\,n'+\sin(\theta)\,t\times n')\tag{1} $$ and $$ \tilde\sigma'=\partial_\theta\sigma=a(-\sin(\theta)n+\cos(\theta)t\times n)\tag{2} $$ Since $$ \tilde\sigma''=\partial_\theta^2\sigma=-a(\cos(\theta)n+\sin(\theta)t\times n)\tag{3} $$ is perpendicular to both, it is perpendicular to the surface. Therefore, $\tilde\sigma$ is a geodesic for each $s$.
HINT:
Any curve of intersection produced by normal section of this argument cannot or should not be used for arriving at the result. One special case is a sphere cut along any great circle.