Here is just an elaboration of Beginner's and user641's answers:
Using the presentation
$$Q_8=\langle a,b\mid a^4=1, \ a^2=b^2, \ b^{-1}ab=a^{-1}\rangle,$$
one can show the following:
Proposition 1. Let
$$A\mathrel{\mathop:}=\{(a,b)\in Q_8^2\mid |a|=4,\ |b|=4,\ a\neq b,\ a\neq b^{-1}\}.$$
Then there is a bijection
$$\Psi:\operatorname{Aut}(Q_8)\to A,\qquad\xi\mapsto(\xi(i),\xi(j)).$$
Using this proposition, one can actually construct the automorphisms on $Q_8$. In particular, counting the number of elements of $A$ gives $|\operatorname{Aut}(Q_8)|=24$.
$Q_8$ has exactly 3 subgroups of order 4, namely $\langle i\rangle$, $\langle j\rangle$, and $\langle k\rangle$. Hence, $\operatorname{Aut}(Q_8)$ acts on $A\mathrel{\mathop:}=\{ \langle i\rangle, \langle j\rangle, \langle k\rangle\}$. Let
$$\pi:\operatorname{Aut}(Q_8)\to S_A$$
be the associated permutation representation. For brevity, let us write $1\mathrel{\mathop:}=\langle i\rangle$, $2\mathrel{\mathop:}=\langle j\rangle$, $3\mathrel{\mathop:}=\langle k\rangle$, so that $A=\{1,2,3\}$ and $S_A=S_3$.
Now, there is an isomorphism
$$S_3\xrightarrow{\sim}\langle a,b\mid a^2=b^2=1,\ (ab)^3=1\rangle,$$
such that $(12)\mapsto a$ and $(13)\mapsto b$.
Using this presentation, one can show that there is a group homomorphism
$$\Psi:S_3\to\operatorname{Aut}(Q_8)$$
such that $(12)\mapsto\tau$ and $(23)\mapsto\sigma$, where
$$\tau\mathrel{\mathop:}=(ij)(-i-j)(k-k)\qquad\mbox{and}\qquad\sigma\mathrel{\mathop:}=(i-i)(jk)(-j-k),$$
if you will pardon my cycle notation. (It doesn't look nice, but there is no ambiguity.)
One can verify that
$\pi\circ\Psi$ is the identity map on $S_3$. This implies that $\pi$ is surjective and $\Psi$ is injective. Also, $\operatorname{Im}\Psi\cap\ker\pi=1$.
$\pi$ therefore factors through the isomorphism
$$\frac{\operatorname{Aut}(Q_8)}{\ker\pi}\xrightarrow{\sim}S_3,$$
from which it follows that $|\ker\pi|=4$.
Indeed, using Propsition 1, one can see that
$$\ker\pi=\{1,\ (i-i)(k-k),\ (j-j)(k-k),\ (i-i)(j-j)\}\simeq V_4,$$
the Klein four-group.
Now, every subgroup of $Q_8$ is normal, so
$$\operatorname{Inn}(Q_8)\subseteq\ker\pi.$$
On the other hand, $Z(Q_8)=\{1,-1\}$ and
$$\operatorname{Inn}(Q_8)\simeq\frac{Q_8}{Z(Q_8)},$$
so $|\operatorname{Inn}(Q_8)|=4$. This implies that
$$\operatorname{Inn}(Q_8)=\ker\pi.$$
Let $H\mathrel{\mathop:}=\operatorname{Im}\Psi$. Since $H\cap\operatorname{Inn}(Q_8)=1$,
$$|\operatorname{Inn}(Q_8)H|=|V_4||S_3|=4\cdot6=24=|\operatorname{Aut}(Q_8)|,$$
i.e.,
$$\operatorname{Inn}(Q_8)H=\operatorname{Aut}(Q_8).$$
Using Proposition 1 once again, one can see that
$$\eta\mathrel{\mathop:}=(i-j)(-ij)(k-k)$$
is an automorphism on $Q_8$.
There is an isomorphism
$$S_4\xrightarrow{\sim}\langle a,b,c\mid a^2=b^2=1, \ (ab)^3=(bc)^3=1, \ (ac)^2=1\rangle$$
such that $(12)\mapsto a$, $(23)\mapsto b$, and $(34)\mapsto c$.
Using this presentation, one can show that there is a group homomorphism
$$\Phi:S_4\to\operatorname{Aut}(Q_8)$$
such that $(12)\mapsto\tau$, $(23)\mapsto\sigma$, and $(34)\mapsto\eta$.
Note that $\Phi|_{S_3}=\Psi$, so $\Phi$ restricts to an isomorphism
$$S_3\xrightarrow{\sim}H.$$
Also, one can check that $\Phi$ restricts to an isomorphism
$$V\xrightarrow{\sim}\operatorname{Inn}(Q_8),$$
where
$$V\mathrel{\mathop:}=\{1,(12)(34),(13)(24),(14)(23)\}\subseteq S_4$$
is a subgroup.
(Counting the number of elements in the conjugacy classes of $S_4$ reveals that the only nontrivial proper normal subgroups of $S_4$ are $V$ and $A_4$.)
Note that $V\cap S_3=1$, so $S_4=VS_3$.
Also, $\operatorname{Aut}(Q_8)=\operatorname{Inn}(Q_8)H$, so the restricted isomorphisms $V\simeq \operatorname{Inn}(Q_8)$ and $S_3\simeq H$ imply that $\Phi$ is surjective, i.e., it is an isomorphism.