$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!
An algebraic example was given in the comments, so here's a topological counterexample.
The forgetful functor $U$ from the category $\mathcal{Top}$ of topological spaces and continuous maps to the category $\mathcal{Set}$ of sets has a left adjoint $D$ which takes a set to the discrete space on that set.
$D$ is fully faithful, since a continuous map between discrete spaces is the same as a function between the underlying sets. More formally, given two sets $X$ and $Y$, every map between $D(X)$ and $D(Y)$ is equal to $D(f)$ for a unique function $f \colon X \to Y$.
However, $U$ is not fully faithful. Given topological spaces $X$ and $Y$, there are (in general) far fewer continuous functions between $X$ and $Y$ than there are functions between $U(X)$ and $U(Y)$.
Best Answer
What it means for a functor $F : \mathcal{C} \to \mathcal{D}$ to be faithful is that, for each $A,B \in \mathrm{ob}(\mathcal{C})$, the function $\mathrm{Hom}_{\mathcal{C}}(A,B) \to \mathrm{Hom}_{\mathcal{D}}(FA, FB)$ is an injection (i.e. a monomorphism in $\mathbf{Set}$). Note that this condition only talks about the morphisms of $\mathcal{D}$, so for instance $F$ could in theory send every object of $\mathcal{C}$ to a single object of $\mathcal{D}$ and still be faithful.
On the other hand, the monomorphisms $F : \mathcal{C} \to \mathcal{D}$ are precisely the embeddings, which are functors that are faithful and injective on objects, so that distinct objects of $\mathcal{C}$ are sent to distinct objects of $\mathcal{D}$. So every monomorphism in $\mathbf{Cat}$ is a faithful functor, but not every faithful functor is a monomorphism.
Epimorphisms in $\mathbf{Cat}$ are a bit trickier to pin down, so I don't think the relationship between epimorphisms and full functors will be quite as easy to describe.