Things simplify a lot if we assume that the primary curve $\alpha$ is given with its arc length as parameter:
$$\alpha:\quad s\mapsto z(s):=\bigl(x(s),y(s)\bigr)\ .$$
Its tangent vector $t(s):=\bigl(\dot x(s),\dot y(s)\bigr)$ as well as its normal vector $n(s):=\bigl(-\dot y(s),\dot x(s)\bigr)$ are then automatically unit vectors. I omit the "$(s)$" in the sequel. Let $\theta:={\rm arg\,}t$ be the polar angle of $t$. The curvature $\kappa$ along $\alpha$ is then given by
$$\kappa:=\dot\theta=\dot x\ddot y-\dot y\ddot x\ .$$
As $\dot x^2+\dot y^2\equiv1$ one has $\dot x\ddot x+\dot y\ddot y=0$, and this implies
$$\kappa\dot x=(\dot x\ddot y-\dot y\ddot x)\dot x=(\dot x^2+\dot y^2)\ddot y=\ddot y,\qquad \kappa\dot y=-\ddot x\ .\tag{1}$$
Consider now the evolute $\beta$ of $\alpha$. For its construction let $\rho(s):={1\over\kappa(s)}$ be the curvature radius of $\alpha$ at $z(s)$. A parametric representation of $\beta$ is then given by
$$\beta:\quad s\mapsto e(s):=z(s)+\rho(s)\>n(s)\tag{2}$$
(of course $s$ is not the arc length parameter on $\beta$). We now look at the tangent vectors to $\beta$. From $(2)$ we get
$$\dot e=(\dot x,\dot y)+\rho(-\ddot y,\ddot x)+\dot\rho\>n\ .\tag{3}$$
From $(1)$ and $\rho\kappa=1$ it then follows that the first two terms in $(3)$ cancel, so that we are left with
$$\dot e=\dot\rho\>n\ .$$
From this we can draw the following conclusion: The evolute point $e(s)$ lies on the normal (a line $\nu=\nu(s)$) to the curve $\alpha$ at $z(s)$, and the tangent to $\beta$ at $e(s)$ is parallel to this line $\nu$. It follows that the family ${\cal N}$ of normals $\nu(s)$ is the family of tangents to $\beta$, so that $\beta$ is indeed the envelope of the family ${\cal N}$.
(I have omitted some technical assumptions about nonvanishing of certain quantities.)
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$.
Best Answer
You can restrict yourself to an arc length parametrization of the curve $\alpha$ (ask for details if it is not clear why this is!).
Then compute $$\beta'(t)=\alpha'(t)-\frac{k'(t)}{k(t)^2}n(t)+\frac{1}{k(t)}n'(t).$$ To answer your question you need to show $\langle \beta'(t),\alpha'(t)\rangle=0$. This follows directly if you use $\langle \alpha''(t),n(t)\rangle =- \langle \alpha'(t),n'(t)\rangle$ which follows from differentiating $\langle \alpha'(t),n(t)\rangle =-0$ with respect to $t$. Then use $\alpha''(t)=k(t)n(t)$.
EDIT: What do you mean by "the normal"? EDIT: Added missing sign.
EDIT: I obtain in my way $\beta'(t)=-\frac{k'}{k^2}n(t).$