I am following Hodges' Shorter Model Theory and I am not sure how to prove this:
Since $C$ applies to all structures in K, that includes $A$ and $B$. So instantiating $C$ as $B$ and $A$ we get a unique homomorphism $f: A \to B$ and $g:B\to A$. So we just need to prove that $f$ has a surjective (onto) embedding.
To have an embedding means 1) there is a one-one $f: A \to B$. We also need to prove 2) $(a_0,...,a_{n-1})\in R^A \iff (fa_0,...,fa_{n-1})\in R^B$. And lastly we need to prove that 3) $f$ is onto.
1) For all $a,a'\in A$, assuming $f(a)=f(a')$, we need to prove $a=a'$.
We are also allowed to assume that there is a unique homomorphic $f:A\to B$. So I need to prove this for constants, functions and relations. But I can't even do it for the constants.
Proving this for constants means we can assume $f(c^A)=f(c'^A)$, and must show $c^A=c'^A$. By def. of homomorphism, $f(c^A)=c^B=f(c'^A)$.
Here I am stuck. My understanding of (2.1 below in the def.) $f(c^A)=c^B$ is that if you input $c$ you will also get $c$ - it's just that former is a symbol in $A$ whereas the latter is in $B$ (Is this correct? I feel I am misunderstanding how constants behaviour with respect to homomorphic functions). So, $f(c^A)=c^B=f(c'^A)$ is really saying $c^a=c^B=c'^A$, we get what we want. But this somehow feels wrong.
2) For all $a$ from $A$, $(a_0,...,a_{n-1})\in R^A \iff (fa_0,...,fa_{n-1})\in R^B$
The homomorphic $f$ has already given us left to right; so we just need to prove right to left. So we assume $(fa_0,...,fa_{n-1})\in R^B$.
But we also have $g:B\to A$, i.e. $(b_0,...,b_{n-1})\in R^B\to (g(b_0),...g(b_{n-1}))\in R^A$.
I need to somehow get $fa_{n}=b_n$, because then I would be able to use the antecedent to get something close to what I need; but I don't know how. (Also would need to show that $a_n=g(b_0)$ presumably)
Here is the definition of homomorphism from Hodges' book: 
This fact admits a essentially category-theoretic proof, where you don't have to think about constant, function, and relation symbols at all!
There is a unique homomorphism $f\colon A\to B$ and a unique homomorphism $g\colon B\to A$. Composing these gives homomorphisms $gf\colon A\to A$ and $fg\colon B\to B$. Since the identity maps $1_A\colon A\to A$ and $1_B\colon B\to B$ are also homomorphisms, by uniqueness we must have $1_A = gf$ and $1_B = fg$. Thus $f$ and $g$ are inverses, so they are isomorphisms.
Of course, in this proof I used freely the basic properties of model-theoretic homomorphisms, which are listed (mostly without proof) in Theorem 1.2.1 of Hodges. Namely: 1.2.1(a) if $f$ and $g$ are homomorphisms, so is their composition $fg$, 1.2.1(c) the identity map $1_A$ is a homomorphism, and 1.2.1(e) an invertible homomorphism is an isomorphism.
From your question, it seems like you have some serious confusions about the definitions, so these facts may not seem obvious to you. It would be a good idea to make sure you can carefully prove all the parts of Theorem 1.2.1 on your own before proceeding further!
Edit: You wrote
This is a major confusion. The statement "for all $a,a'\in A$, if $f(a) = f(a')$, then $a = a'$" is just the definition of "$f$ is injective". Here $a$ and $a'$ are just elements of $A$, they're not symbols in the language. It doesn't make any sense to "prove this for constants, functions and relations". The language is not involved here at all!
You can show directly that $f$ is injective by noting that for all $a,a'\in A$, if $f(a) = f(a')$, then $g(f(a)) = g(f(a'))$, and here you need to make the observation in my solution above that $gf = 1_A$, so $a = 1_A(a) = g(f(a)) = g(f(a')) = 1_A(a') = a'$.