$Cat(A,B)$ is the set of functors from the category $A$ to the category $B$. In general, $\mathcal{C}(A,B)$ denotes the hom-set between objects $A,B$ in the category $\mathcal{C}$. Since there is a "category of categories", something like $Cat(A \times B, C) \cong Cat(A, C^B)$ is saying that there is a bijection between functors, sending $F:A\times B \rightarrow C$ to the functor $G: A \times C^B$. (This is exactly like saying $$Maps(A \times B, C) \cong Maps(A, C^B)$$ in $Sets$, except the functions are now functors!) What is $G$? Well, $C^B$ is a functor category. The objects are functors, and so given an object $a$ of $A$, $G(a)$ had better be a functor from $B$ to $C$. What functor do we take? The only option is $F(a,-)$. But $G$ also needs to do something to morphisms. So a morphism $k:a \rightarrow a'$ needs to go to a natural transformation $F(a,-) \rightarrow F(a',-)$. But this comes built in to the definition of $F$, since it's natural in both slots. We can also go back. Given such a $G$, we can build an $F$, and do it in a way that the two constructions are mutually inverse.
Now, you can then view $Cat(A,B)$ as a category (a functor category), with objects the morphisms and morphisms as natural transformations between them. The above construction doesn't "come with" a way to send morphisms (natural transformations) to morphisms. But given a natural transformation between bifunctors $S \Rightarrow T:A \times B \rightarrow C$, I would believe that one could construct a natural transformation between the adjoints, which I'll denote $\hat{S}$ and $\hat{T}$. If $\eta$ is the natural transformation from $S$ to $T$, then define $\hat{\eta}$ at $a$ to be... what? Well, it needs to go from $\hat{S}(a)$ to $\hat{T}(a)$. These are objects in the functor category $Cat(B,C)$, so $\hat{S}(a)$ is a functor from $B$ to $C$, as is $\hat{T}(a)$. So $\eta_a$ should be a natural transformation! What should the natural transformation be? Well, I would use $\eta(a,-)$.
I don't have any reason to think that this $\hat{\cdot}$ operation won't induce a bijection on natural transformations, and so those two functor categories are indeed isomorphic, which you could write as $$C^{A\times B} = (C^B)^A.$$ But you can probably imagine that writing out the details is a little tedious! The trick is to at all times carefully keep track of what type of objects you're working with, what the morphisms should be, etc.
Note that naturality of the bijection $Cat(A\times B,C) \cong Cat(A,C^B)$ didn't enter with this argument, since we never had to think about any categories other than $A,B,$ and $C$. So what does that mean? Go back to the thing that took a functor $F:A \times B \rightarrow C$ and spat out a functor $G:A \rightarrow C^B$. Suppose you had a functor $H:A' \rightarrow A$. You can use this to build a functor $H\times 1:A' \times B \rightarrow A \times B$. Suppose you wanted to know what happens when you applied all this stuff to $F(H\times 1):A' \times B \rightarrow C$. You have to go through all that computation over again!
But that's where naturality saves the day. Naturality says that if you've computed one thing, you can compute pre- and post- compositions by just... composing! So the result from applying all this to $F(H \times 1)$ is just $GH: A' \rightarrow A \rightarrow C^B$. As you read the book, you'll notice that naturality is a very powerful condition, since it imposes so many relations on the transformation!
Remember that you don't have to define Hom functors from scratch; you should already know how they work. Given $\langle f,g,h\rangle:\langle A,B,C\rangle\to\langle A',B',C'\rangle$, $F(f,g,h)(a:A\times B\to C)$ is just $a\mapsto h\circ a\circ (f\times g)$. (Notice that you have the variance backwards above--the first argument of a Hom functor is contravariant, the second covariant.) $G$ requires a little more thought, but it's easy to sort out with a little time.
$H$ is, I think, where you're getting confused. All you need to show is that for every $A,B,C$ there's a function between sets $H_{A,B,C}:F(A,B,C)\to G(A,B,C)$ that commutes with the $F(f,g,h)$ and the $G(f,g,h)$. That's it. You don't need any extra functors. These functions are given by the currying operation described above.
Best Answer
For simplicity, let's just fix $B$ and $C$ and focus on naturality in $A.$ If we want to look at this in terms of functors, the functors in question are $\operatorname{Cat}(-\times B,C)$ and $\operatorname{Cat}(-, C^B)$ and we want to show that $\phi$ is an arrow between these two functors in the appropriate category (in this case $\mathrm{Set}^{\mathrm{Cat}^{\mathrm{op}}}$), which means we want to show that $\phi_A:\operatorname{Cat}(A\times B,C) \to \operatorname{Cat}(A, C^B)$ can be regarded as the $A$-th component of a natural transformation between the functors $\operatorname{Cat}(-\times B,C)$ and $\operatorname{Cat}(-, C^B).$
Given an arrow $g:A'\to A,$ the first functor takes an arrow $f:A\times B\to C$ to $f\circ (g\times id_{B})$ and given an arrow $h: A\to C^B,$ the second functor takes $h$ to $h\circ g.$ So showing naturality means showing that for any $f:A\times B \to C,$ $\phi_{A'}(f\circ (g\times id_B)) = \phi_A(f)\circ g.$ We can verify this by looking at how each side acts on some $a\in A'$ (either an object or arrow.. no matter). The left-hand side is $$ \phi_{A'}(f\circ (g\times id_B)) (a) = f\circ (g\times id_B)(a,-) = f(g(a), -)$$ and the right-hand side is $$ (\phi_A(f)\circ g) (a) = \phi_A(f)(g(a)) = f(g(a),-),$$ which are the same, so we're done.
Note that for most of the formality here, it was completely irrelevant that the arrows in question were functors. For everything up till the verification of the equation at the end, we may as well have replaced Cat with Set or any other cartesian closed category. Only in verifying the equation did we actually think about what the category actually was, and even then not really... we could have done that step just in terms of the eval arrow, etc, it just might have looked a little more obscure.
Naturality in $B$ and $C$ can be shown similarly. It can be tediously shown that in general, verifying each component's naturality separately is all that is required to show the whole thing is natural, i.e. that $\phi$ is an arrow in the functor category $\operatorname{Set}^{\operatorname{Cat}^{\mathrm{op}}\times \operatorname{Cat}^{\mathrm{op}}\times \operatorname{Cat}}.$ (And it can also be shown that all it takes to be an isomorphism in said category is for each component of the natural transformation to be an isomorphism.)