Like Qiaochu says, the key here is that the direct product of finitely many abelian groups functions as both the (categorical) product and the (categorical) coproduct in the category of abelian groups.
And before your eyes glaze over, what that means is that:
A homomorphism from an abelian group $A$ into a (finite) direct product $G_1\times G_2\times\cdots\times G_n$ of abelian groups is equivalent to a family $f_1,\ldots,f_n$ of homomorphisms $f_i\colon A\to G_i$; (in fact, this holds for arbitrary groups, and arbitrarily many direct factors, not just finitely many); and
A homomorphism from a finite direct product $G_1\times G_2\times\cdots\times G_n$ of abelian groups into an abelian group $B$ is equivalent to a family $g_1,\ldots,g_n$ of homomorphisms $g_i\colon G_i\to B$ (here we do need both finiteness and abelianness).
The first equivalence is easy: given a map $f\colon A\to G_1\times\cdots\times G_n$, the maps $f_i$ are just the compositions of $f$ with the canonical projections $\pi_i\colon G_1\times\cdots\times G_n\to G_i$; going the other way, given a family $f_1,\ldots,f_n$ of maps, you get the map $A\to G_1\times\cdots\times G_n$ by $f(a) = (f_1(a),f_2(a),\ldots,f_n(a))$.
For the second equivalence, given a homomorphism $g\colon G_1\times\cdots\times G_n\to B$, we define the maps $g_i\colon G_i\to B$ by restricting $g$ to the subgroup $\{0\}\times\cdots \times \{0\}\times B_i\times\{0\}\times\cdots\times\{0\}$. Conversely, given a family of homomorphisms $g_1,\ldots,g_n$, we construct the map $g$ by $g(x_1,\ldots,x_n) = g_1(x_1)+g_2(x_2)+\cdots+g_n(x_n)$; here, both the fact that the product has only finitely many factors and that the groups are abelian is important.
Now let $A=B=G_1\times\cdots\times G_n$. Then a homomorphism from $A$ to $B$ is equivalent, by 1, to a family of homomorphisms $\Phi_j\colon A\to G_j$. And by 2, each $\Phi_j$ is equivalent to a family of homomorphisms $\phi_{ij}\colon G_i\to G_j$. Thus, each homomorphism from $A$ to $B$ is equivalent to a family $\{\phi_{ij}\mid 1\leq i,j\leq n\}$, with $\phi_{ij}\colon G_i\to G_j$.
Now suppose you have two homomorphisms, $\Phi,\Psi\colon A\to B$, and you want to compose them. If $\Phi$ corresponds to $\{\phi_{ij}\}$ and $\Psi$ corresponds to $\{\psi_{ij}\}$, what does the composition correspond to in terms of maps $G_i\to G_j$?
If you trace the correspondence carefully, you should find that the induced map from $G_i$ to $G_j$ is precisely
$$\psi_{i1}\circ\phi_{1j} + \psi_{i2}\circ\phi_{2j}+\cdots+\psi_{in}\circ\phi_{nj},$$
so that if you arrange the families $\{\phi_{ij}\}$ and $\{\psi_{ij}\}$ into matrices, composition corresponds to matrix multiplication in the usual way (though because composition is not commutative, you have to be mindful of the order of the products.
Once you have that endomorphisms can be "coded" as matrices with composition corresponding to matrix multiplication, the fact that automorphisms correspond to invertible matrices follows immediately. However, actually writing down a formula is complicated, because these matrices have entries that don't commute with one another; even in simple cases, like trying to do something like $C_{p^{\alpha}}\times C_{p^{\beta}}$ with $\alpha\gt\beta$, writing down the inverse of an automorphism in terms of its entries turns into a computation with congruences that is difficult to write down as a formula. But never fret, you aren't asked for an explicit formula.
Even without the classification of finite simple groups, quite reasonable bounds are known, for example in work of P.M. Neumann. If the group $G$ can be generated by $r$ but no fewer elements, then no automorphism of $G$ can fix the $r$ given generators, so there are at most $\prod_{j=1}^{r} (|G|-j)$ different automorphisms of $G,$ since the $r$ generators must have distinct images, none of which is the identity. As P.M. Neumann has observed, $G$ can always by generated by ${\rm log}_{2}(|G|)$ or fewer elements, so we have $r \leq \lfloor {\rm log}_{2}(|G|) \rfloor .$ For $|G| >4,$ this always gives a strictly better bound for the size of ${\rm Aut}(G)$ than $(|G|-1)!.$ For large $|G|,$ it is much better. Using the classification of finite simple groups, much better bounds are known.
Later edit: Perhaps I could outline Neumann's argument, since it is quite elementary, and I do not remember a reference: Let $\{x_1, x_2, \ldots, x_r \}$ be a minimal generating set for $G$ and let $G_i = \langle x_1, x_2, \ldots, x_i \rangle $ for $i >0,$ $G_{0} = \{ e \}.$ Then for $1 \leq i \leq r,$ we have $|G_i| > |G_{i-1}|$ by minimality of the generating set. Furthermore, $|G_i|$ is divisible by $|G_{i-1}|$ by Lagrange's theorem, so $|G_i| \geq 2|G_{i-1}|.$ Hence $|G| = |G_r| \geq 2^r.$
Best Answer
You're on the right track. Your argument about "building an automorphism" shows that $\operatorname{Aut} G \times \operatorname{Aut} H$ is contained in $\operatorname{Aut} (G\times H)$.
Note that your argument does not make use of the assumption that $G$ and $H$ have relatively prime orders. Thus it shows that $\operatorname{Aut} G \times \operatorname{Aut} H$ is always contained in $\operatorname{Aut} (G\times H)$, regardless of the group orders.
What's missing is an argument that $\operatorname{Aut} (G\times H)$ doesn't have anything in it besides the things coming from $\operatorname{Aut} G\times\operatorname{Aut} H$. This is the part of the claim that depends on the assumption that $G$ and $H$ have relatively prime orders. Indeed, without this assumption, it's not true: for example if $G$ and $H$ are both cyclic of prime order $p$, then $\operatorname{Aut} (G\times H)$ is actually $GL(2,\mathbb{F}_p)$, which is significantly bigger than $\operatorname{Aut} G \times \operatorname{Aut} H = \mathbb{F}_p^\times \times\mathbb{F}_p^\times$. This is because there exist automorphisms that "mix up" $G$ and $H$. For example if $G=H=(\mathbb{F}_p,+)$, then there is an automorphism that fixes $(1,0)$ (so $G\times\{0\}$ stays inside $G\times\{0\}$), but sends $(0,1)$ to $(1,1)$ (so $\{0\}\times H$ is moved by the automorphism to somewhere else).
G. Sassatelli's hint is aimed at showing how you can rule out the possibility that $G\times H$ has any automorphisms that "mix up" the $G$ part (which is $G\times\{\text{identity in $H$}\}$) and the $H$ part (i.e. $\{\text{identity in $G$}\}\times H$). Use the fact that $G,H$ have prime orders.
(In case the phrase "characteristic subgroup" is new to you, it means a subgroup that is not moved to somewhere else by any automorphism.)