This is exercise $2.2.7$ in Pressley's Elementary Differential Geometry (which has solution sketches in the back of the text). I've expanded a bit on the solution provided.
Hints:
For signed curvature, what is the definition of signed curvature in terms of your signed normal and tangent? Remember that you're trying to find $\kappa_{s_{\epsilon}}$.
For the normal line part, what does it mean for a line to be tangent to $\epsilon$? What does a normal line at a specific point $s_0$ look like? We calculated the tangent to $\epsilon$ in the first part.
(More complete answer below)
$$\epsilon (s)=\gamma (s)+\frac{1}{\kappa_s(s)}n_s(s)$$
$\textbf{1.}$ We show that the arc length of $\epsilon$ is $\frac{-1}{\kappa_s(s)}$ up to a constant. First off, I'm going to forget about the $s$ notation-wise so assume everything is a function of $s$ unless stated otherwise.
Well, we take the derivative of $\epsilon$ with respect to $s$ to get the arc length:
$$\dot{\epsilon} = \dot{\gamma} + \frac{1}{\kappa_s}(-\kappa_s \mathbf{t})-\frac{\dot{\kappa_s} \mathbf{n_s}}{\kappa_s^2}=-\frac{\dot{\kappa_s} \mathbf{n_s}}{\kappa_s^2}$$
(recall $\mathbf{\dot{t}} = \kappa_s \mathbf{n_s} \implies \mathbf{\dot{n_s}} = -\kappa_s \mathbf{t}$ for a unit-speed curve since $\mathbf{n_s} \cdot \mathbf{t} = 0$ so $\mathbf{\dot{n_s}} \cdot \mathbf{t} + \mathbf{n_s} \cdot \mathbf{\dot{t}} = 0 \implies \mathbf{\dot{n_s}} \cdot \mathbf{t}= - \kappa_s(\mathbf{n_s \cdot n_s}) = -\kappa_s \implies \mathbf{\dot{n_s}}(\mathbf{t}\cdot \mathbf{t}) = \mathbf{\dot{n_s}} = -\kappa_s \mathbf{t}$)
Now, the arc length is given by
$$u=\int \| \dot{\epsilon} \| \,ds = \int \frac{\dot{\kappa_s}}{\kappa_s^2} \,ds = -\frac{1}{\kappa_s} + C$$
Note that the second equality holds since we assumed $\dot{\kappa_s} > 0$.
$\textbf{2.}$ We calculate the signed curvature $\kappa_{s_{\epsilon}}.$ Recall the signed curvature is the rate at which the tangent vector rotates. In particular,
$$\mathbf{\dot{t}}_{\epsilon} = \kappa_{s_{\epsilon}}\mathbf{n_s}_{\epsilon}$$ In this case, we take the tangent vector to be $\mathbf{t}_{\epsilon}=-\mathbf{n_s}$. Rotating the tangent vector counterclockwise by $-\pi/2$ gives us our signed unit normal. In particular, the signed normal is just $\mathbf{n_s}_{\epsilon}=\mathbf{t}$. Now,
$$\frac{d (-\mathbf{n_s})}{\,du} = \kappa_s \mathbf{t} \frac{ds}{du} = \kappa_s \mathbf{t} \frac{\kappa_s^2}{\dot{\kappa_s}}= \frac{\kappa_s^3}{\dot{\kappa_s}}\mathbf{t}= \kappa_{s_{\epsilon}}\mathbf{n_s}_{\epsilon}$$
In particular, since the derivative of the tangent vector is the signed curvature times the signed unit normal, dotting the derivative of the tangent vector with the signed unit normal gives the result. That is, take the dot product of the above expression with $\mathbf{t}$ to get the signed curvature of $\epsilon$:
$$\frac{\kappa_s^3}{\dot{\kappa_s}}$$
$\textbf{3.}$ We show that all normal lines to $\gamma$ are tangent to $\epsilon$.
Well, let's look at a point on the normal line at $\gamma(s_0)$ for some arbitrary $s_0$. It looks like $\gamma(s_0) + C\mathbf{n_s}(s_0)$ for some $C$. Since $\epsilon(s_0) = \gamma(s_0) + \frac{1}{\kappa_s(s_0)}\mathbf{n_s}(s_0)$, the intersection occurs when $C=\frac{1}{\kappa_s(s_0)}$. Well, we calculated the tangent of $\epsilon$ at $s_0$:
$$\dot{\epsilon}(s_0)=-\frac{\dot{\kappa_s(s_0)} \mathbf{n_s}(s_0)}{\kappa_s^2(s_0)}$$
so that the tangent there is parallel to $\mathbf{n_s}(s_0)$.
$\textbf{4.}$ Regarding the evolute of the cycloid, this is just a computation, with a lot of the steps highlighted above. Regarding the reparameterization, consider $\tilde{t} = t + \pi$.
There's no reason to use polar coordinates, actually. But, yes, $\theta(s)$ is the angle the unit tangent at arclength $s$ makes with the positive $x$-axis. It is standard that the signed curvature is $\theta'(s)$ (the rate of turning of the unit tangent vector). If you don't know that, here's the easy argument: Write $\vec T(s) = (\cos\theta(s),\sin\theta(s))$. Then
$$\vec T'(s) = (-\sin\theta(s),\cos\theta(s))\theta'(s) = \kappa_s(s)\vec N(s).$$
(Remember that in the case of plane curves, we always take $\vec T,\vec N$ to be a right-handed basis.)
Best Answer
The reason for the signed in the definition is that you want to rule out a point like the origin on $y=x^3$. The signed curvature of this curve is $\kappa_s(x) = \dfrac{6x}{(1+9x^4)^{3/2}}$, and it has no critical point at $x=0$. However, the unsigned curvature $\kappa = |\kappa_s|$ has a minimum at $x=0$ (although it is not differentiable there).
Vertices should correspond to extreme points of curvature, not just any old critical points.
If you do not like the lack of differentiability of $\kappa$ in the example, change to $y=x^5$ instead. The same phenomenon persists, but now $\kappa$ will be differentiable at $x=0$.