The correct condition is that $m$ and $n$ are coprime, that is, have no common factors. In particular, this means that $C_2 \times C_3 \cong C_6$. (Sometimes it is hard to compare two multiplication tables by inspection, though it can help identifying two isomorphic groups from their tables by reordering the elements.)
Hint Given two groups $G, H$ and elements $a \in G, b \in H$, the order of element $(a, b)$ is the smallest number, $\text{lcm}(k, l)$ divisible by both the order of $l$ of $a$ and the order $k$ of $b$.
In particular, suppose $G$ and $H$ are cyclic, say $G = C_n$, $H = C_m$. Then, if $a$ and $b$ are generators of $C_n$, $C_m$, respectively, by definition they have respective orders $n, m$ and hence $(a, b) \in C_n \times C_m$ has order $\text{lcm}(m, n)$.
So, if $m, n$ are coprime, this order is $\text{lcm}(m, n) = mn$.
Conversely, if $m, n$ are not coprime, then since any $a \in C_n$ has order $l$ dividing $n$ and any $b \in C_m$ has order $k$ dividing $m$, we have that the generic element $(a, b) \in C_n \times C_m$ has order $\text{lcm}(k, l) \leq \text{lcm}(m, n) < mn$. In particular, no element has order $mn$, so $C_m \times C_n$ is not cyclic.
For example, the elements $1 \in C_2$ and $1 \in C_3$ generate their respective groups, and the powers of $(1, 1) \in C_2 \times C_3$ are
$$(1, 1), (0, 2), (1, 0), (0, 1), (1, 2), (0, 0),$$
so $(1, 1)$ generates all of $C_2 \times C_3$, which is hence isomorphic to $C_6$.
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
The main technique is the Chinese remainder theorem: $C_m \times C_n \cong C_{mn}$ when $\gcd(m,n)=1$, which follows directly from your two pieces of knowledge.
This gives at once that $C_4 \times C_{25}$ is isomorphic to $C_{100}$.
Using the Chinese remainder theorem repeatedly, you can decompose any direct product of several cyclic groups into a direct product of cyclic groups of prime-power order ($p$-groups); this is called the primary decomposition.
From the primary decomposition, you can reassemble the factors into the form $C_{d_1} \times C_{d_1} \times \cdots \times C_{d_n}$ with $d_1 \mid d_2 \mid \cdots \mid d_n$; this called the invariant factor decomposition.
Both forms are canonical forms and two direct product of cyclic groups are isomorphic iff they have the same canonical forms.
All this is the easy part of the structure theorems for finite abelian groups. The hard part is proving that every finite abelian group is a direct product of cyclic groups. See Simple proof of the structure theorems for finite abelian groups. Uniqueness also takes some work.