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.
The quaternion group is indeed the minimal counter-example. Clearly, any group of orders $1,2,3,5$ or $7$ is cyclic, and the two (non-isomorphic) groups of order $4$ are:
$\Bbb Z_4$ and $\Bbb Z_2 \times \Bbb Z_2$.
There are likewise just two non-isomorphic groups of order $6$:
$\Bbb Z_6$ and $S_3 \cong \Bbb Z_3 \rtimes \Bbb Z_2$ (this is the only possible non-trivial semi-direct product of these two groups, since:
$0 \mapsto 1_{\Bbb Z_3}\\1 \mapsto (x \mapsto -x)$
is the sole non-trivial homomorphism $\Bbb Z_2 \to \text{Aut}(\Bbb Z_3)$).
It is convenient to use this formulation of a(n internal) semi-direct product:
$G = NH$, where $N,H$ are subgroups of $G$, and $N \lhd G$.
$N \cap H = \{e_G\}$.
The problem with obtaining $Q_8$ as a semi-direct product of two proper subgroups, is that we must have either $|H|$ or $|N|$ equal to $2$. But the only subgroup of order $2$ in $Q_8$ is $\{1,-1\}$, which is a subgroup of every subgroup of $Q_8$ of order $4$:
$\langle i\rangle = \{1,-1,i,-i\}\\\langle j\rangle = \{1,-1,j,-j\}\\\langle k\rangle = \{1,-1,k,-k\}$
Note that all $6$ elements of order $4$ lie in one of these $3$ subgroups.
Thus the condition $N \cap H = \{e_G\}$ (which is $=\{1\}$ in this case) is impossible to satisfy.
Best Answer
We'll induct on the number of distinct prime factors in the group's order. As you've said, the base case is pretty easy. Now, suppose the statement has been proven for all abelian groups, $H$, such that $|H|$ has $n$ distinct prime factors.
Let $G$, then, be an abelian group with $n+1$ distinct prime factors. This means that we can factor $|G|$ as $p^kj$ where $p^k$ and $j$ are coprime, and $j$ has $n$ distinct prime factors. Let $P$ be the set of all elements in $G$ whose order divides $p^k$ and let $J$ be the set of all elements in $G$ whose order divides $j$.
It is easy to see that both $P$ and $J$ are subgroups of $G$. It is also easy to see, by Cauchy's theorem, that $|P|$ and $|J|$ must be coprime. This will be important later.
First, each element in $G$ can be expressed as a sum of an element in $P$ and element in $J$. This is relatively easy to show. For any element, $x\in G$, we have $|G|\cdot x=0$, i.e. $(p^kj)\cdot x=0$. But this can be rewritten in a couple of ways- we can write it as $j\cdot (p^k\cdot x)=0$ which gives us that $\operatorname{ord}(p^k\cdot x)|j$.
Similarly, $\operatorname{ord}(j\cdot x)|p^k$. So, by the definitions of $P$ and $J$, for any $x\in G$, $p^k\cdot x\in J$ and $j\cdot x\in P$.
But, since $p^k$ and $j$ are coprime we can pick $a$ and $b$ so that $ap^k+bj=1$, which means $a\cdot(p^k\cdot x)+b\cdot(j\cdot x)=(ap^k)\cdot x+(bj)\cdot x=(ap^k+bj)\cdot x=1\cdot x=x$.
By what we have already shown, $a\cdot(p^k\cdot x)\in J$ and $b\cdot(j\cdot x)\in P$, so each $x\in G$ can be written as the combination of an element in $P$ and an element in $J$.
Also, since the order of any element in $P$ is coprime to the order of any non-zero element in $J$ (by the definitions of $P$ and $J$), we have $P\cap J=\{0\}$.
This finally gives us $G=P\oplus J$. Given that: $|P|$ and $|J|$ are coprime, $|P|=p^s$ for some $s$ (by Cauchy's theorem), and that $|G|=|P||J|$ (because $G$ is the direct sum of $P$ and $J$), we have $|P|=p^k$ and $|J|=j$. Now, we can apply the induction hypothesis on $J$ to expand it as a direct sum of groups of prime order in distinct primes, and, with $G=P\oplus J$, we are done.