[proofplan]
We construct the bijection directly. A natural transformation $\alpha:H_A\to H_B$ is determined by its value on the identity morphism $\operatorname{id}_A:A\to A$, and this value is a morphism $A\to B$. Conversely, every morphism $s:A\to B$ defines a natural transformation by postcomposition. The two constructions are inverse because naturality applied to a morphism $v:X\to A$ forces $\alpha_X(v)=\alpha_A(\operatorname{id}_A)\circ v$.
[/proofplan]
[step:Define evaluation at the identity morphism]
For each natural transformation $\alpha:H_A\to H_B$, define
\begin{align*}
\Phi(\alpha) := \alpha_A(\operatorname{id}_A) \in \operatorname{Hom}_{\mathcal C}(A,B).
\end{align*}
This is well-defined because the component
\begin{align*}
\alpha_A:\operatorname{Hom}_{\mathcal C}(A,A)\to \operatorname{Hom}_{\mathcal C}(A,B)
\end{align*}
has codomain $\operatorname{Hom}_{\mathcal C}(A,B)$.
[/step]
[step:Send a morphism to postcomposition by that morphism]
Let $s\in \operatorname{Hom}_{\mathcal C}(A,B)$. For each object $X\in \operatorname{Ob}(\mathcal C)$, define a map
\begin{align*}
\tau^s_X:\operatorname{Hom}_{\mathcal C}(X,A)&\to \operatorname{Hom}_{\mathcal C}(X,B)\\
v&\mapsto s\circ v.
\end{align*}
We verify that $\tau^s=(\tau^s_X)_X$ is natural. Let $f:Y\to X$ be a morphism in $\mathcal C$, and let $v:X\to A$ be an element of $\operatorname{Hom}_{\mathcal C}(X,A)$. Since $H_A(f)$ and $H_B(f)$ are precomposition by $f$, naturality requires
\begin{align*}
\tau^s_Y(v\circ f)=\tau^s_X(v)\circ f.
\end{align*}
By the definition of $\tau^s$ and associativity of composition in $\mathcal C$,
\begin{align*}
\tau^s_Y(v\circ f)
&= s\circ (v\circ f)\\
&= (s\circ v)\circ f\\
&= \tau^s_X(v)\circ f.
\end{align*}
Thus $\tau^s:H_A\to H_B$ is a natural transformation. Define
\begin{align*}
\Psi:\operatorname{Hom}_{\mathcal C}(A,B)&\to \operatorname{Nat}(H_A,H_B)\\
s&\mapsto \tau^s.
\end{align*}
[guided]
Take a morphism $s:A\to B$. The intended natural transformation should convert each map into $A$ into a map into $B$. If $v:X\to A$, the only available construction is postcomposition:
\begin{align*}
X \xrightarrow{v} A \xrightarrow{s} B.
\end{align*}
So for each object $X$, we define
\begin{align*}
\tau^s_X:\operatorname{Hom}_{\mathcal C}(X,A)&\to \operatorname{Hom}_{\mathcal C}(X,B)\\
v&\mapsto s\circ v.
\end{align*}
We must check that these component maps are natural in $X$. Let $f:Y\to X$ be a morphism of $\mathcal C$. Since $H_A$ and $H_B$ are contravariant, both functors send $f$ to precomposition by $f$. Therefore the naturality condition says that, for every $v:X\to A$,
\begin{align*}
\tau^s_Y(v\circ f)=\tau^s_X(v)\circ f.
\end{align*}
The left-hand side is
\begin{align*}
\tau^s_Y(v\circ f)=s\circ (v\circ f),
\end{align*}
while the right-hand side is
\begin{align*}
\tau^s_X(v)\circ f=(s\circ v)\circ f.
\end{align*}
These are equal by associativity of composition in the category $\mathcal C$. Hence $\tau^s$ is a natural transformation $H_A\to H_B$.
[/guided]
[/step]
[step:Show evaluation after postcomposition recovers the original morphism]
Let $s\in \operatorname{Hom}_{\mathcal C}(A,B)$. Then
\begin{align*}
(\Phi\circ \Psi)(s)
&= \Phi(\tau^s)\\
&= \tau^s_A(\operatorname{id}_A)\\
&= s\circ \operatorname{id}_A\\
&= s.
\end{align*}
Thus $\Phi\circ\Psi=\operatorname{id}_{\operatorname{Hom}_{\mathcal C}(A,B)}$.
[/step]
[step:Use naturality at an arbitrary morphism into $A$]
Let $\alpha:H_A\to H_B$ be a natural transformation. We prove that $\Psi(\Phi(\alpha))=\alpha$.
Let $X\in \operatorname{Ob}(\mathcal C)$, and let $v\in \operatorname{Hom}_{\mathcal C}(X,A)$. Regard $v:X\to A$ as a morphism in $\mathcal C$. Since $H_A$ and $H_B$ are contravariant, the morphism $v:X\to A$ induces maps
\begin{align*}
H_A(v):\operatorname{Hom}_{\mathcal C}(A,A)&\to \operatorname{Hom}_{\mathcal C}(X,A),\\
H_B(v):\operatorname{Hom}_{\mathcal C}(A,B)&\to \operatorname{Hom}_{\mathcal C}(X,B),
\end{align*}
both given by precomposition with $v$. Naturality of $\alpha$ with respect to $v$ gives
\begin{align*}
\alpha_X\bigl(H_A(v)(\operatorname{id}_A)\bigr)
=
H_B(v)\bigl(\alpha_A(\operatorname{id}_A)\bigr).
\end{align*}
Now
\begin{align*}
H_A(v)(\operatorname{id}_A)=\operatorname{id}_A\circ v=v,
\end{align*}
and
\begin{align*}
H_B(v)\bigl(\alpha_A(\operatorname{id}_A)\bigr)
=
\alpha_A(\operatorname{id}_A)\circ v.
\end{align*}
Therefore
\begin{align*}
\alpha_X(v)=\alpha_A(\operatorname{id}_A)\circ v.
\end{align*}
By definition of $\Phi$ and $\Psi$, the component of $\Psi(\Phi(\alpha))$ at $X$ sends $v$ to
\begin{align*}
\Phi(\alpha)\circ v
=
\alpha_A(\operatorname{id}_A)\circ v.
\end{align*}
Hence $\Psi(\Phi(\alpha))_X(v)=\alpha_X(v)$ for every object $X$ and every $v:X\to A$. Thus $\Psi(\Phi(\alpha))=\alpha$.
[guided]
The key point is that naturality tells us what $\alpha_X$ does to every morphism $v:X\to A$ once we know what $\alpha_A$ does to $\operatorname{id}_A$.
Fix an object $X\in \operatorname{Ob}(\mathcal C)$ and a morphism $v:X\to A$. Since $H_A$ is contravariant, the morphism $v:X\to A$ produces a function
\begin{align*}
H_A(v):\operatorname{Hom}_{\mathcal C}(A,A)&\to \operatorname{Hom}_{\mathcal C}(X,A)\\
u&\mapsto u\circ v.
\end{align*}
Similarly, $H_B$ produces
\begin{align*}
H_B(v):\operatorname{Hom}_{\mathcal C}(A,B)&\to \operatorname{Hom}_{\mathcal C}(X,B)\\
w&\mapsto w\circ v.
\end{align*}
Naturality of $\alpha:H_A\to H_B$ with respect to $v:X\to A$ says that the two ways of passing from $\operatorname{Hom}_{\mathcal C}(A,A)$ to $\operatorname{Hom}_{\mathcal C}(X,B)$ agree:
\begin{align*}
\alpha_X\bigl(H_A(v)(u)\bigr)
=
H_B(v)\bigl(\alpha_A(u)\bigr)
\end{align*}
for every $u\in \operatorname{Hom}_{\mathcal C}(A,A)$. We apply this with $u=\operatorname{id}_A$. Then
\begin{align*}
H_A(v)(\operatorname{id}_A)=\operatorname{id}_A\circ v=v,
\end{align*}
and therefore
\begin{align*}
\alpha_X(v)
=
H_B(v)\bigl(\alpha_A(\operatorname{id}_A)\bigr)
=
\alpha_A(\operatorname{id}_A)\circ v.
\end{align*}
This proves that every component $\alpha_X$ is completely determined by the single morphism $\alpha_A(\operatorname{id}_A):A\to B$. But $\Phi(\alpha)$ is defined to be exactly this morphism. Hence $\Psi(\Phi(\alpha))$ sends each $v:X\to A$ to
\begin{align*}
\Phi(\alpha)\circ v
=
\alpha_A(\operatorname{id}_A)\circ v
=
\alpha_X(v).
\end{align*}
So $\Psi(\Phi(\alpha))=\alpha$ as natural transformations.
[/guided]
[/step]
[step:Conclude that the two constructions give the desired natural bijection]
The previous two steps prove
\begin{align*}
\Phi\circ\Psi=\operatorname{id}_{\operatorname{Hom}_{\mathcal C}(A,B)}
\qquad\text{and}\qquad
\Psi\circ\Phi=\operatorname{id}_{\operatorname{Nat}(H_A,H_B)}.
\end{align*}
Therefore $\Phi$ and $\Psi$ are inverse bijections. Hence
\begin{align*}
\operatorname{Nat}(\operatorname{Hom}_{\mathcal C}(-,A),\operatorname{Hom}_{\mathcal C}(-,B))
\cong
\operatorname{Hom}_{\mathcal C}(A,B),
\end{align*}
and under this bijection a morphism $s:A\to B$ corresponds to the natural transformation whose component at $X$ sends $v:X\to A$ to $s\circ v:X\to B$.
[/step]
