Let's assume that the number of 3-Sylow subgroups is 4*
Let $G$ act on the set of 3-Sylow subgroups, and this will give a homomorphism
$$
f : G\to S_4
$$
We claim that this homomorphism is injective, and so an isomorphism.
a) Let $K = \ker(f)$, then $K < N_G(P)$ where $P$ is some fixed 3-Sylow subgroup.
Now,
$$
[G:N_G(P)] = 4 \Rightarrow |N_G(P)| = 6 \Rightarrow N_G(P) \cong \mathbb{Z}_6 \text{ or } S_3
$$
If $N_G(P) \cong \mathbb{Z}_6$, then $G$ would have an element of order 6, and so $N_G(P) \cong S_3$, and so
$$
|K| \in \{1,3,6\}
$$
(Note $|K| \neq 2$ since $S_3$ has no normal subgroups of order 2)
b) If $|K| = 1$ we're done and if $|K| = 6$, then $K = N_G(P) \triangleleft G$, but $N_G(N_G(P)) = N_G(P)$ which is a contradiction. Hence, assume $|K| = 3$
c) If $|K| =3$, then by the N/C theorem,
$$
G/C_G(K) = N_G(K)/C_G(K) \cong \text{ a subgroup of } Aut(\mathbb{Z}_3) \cong \mathbb{Z}_2
$$
In particular, $2 \mid C_G(K)$, so $C_G(K)$ contains an element of order 2, which, when multiplied with a generator of $K$ will give an element of order 6 - a contradiction.
Thus, $|K| = 1$ and we're done.
$\ast$ All that remains to show is that $n_3 = 4$, or equivalently, $n_3 \neq 1$ : I believe that a unique (and hence normal) 3-Sylow subgroup would end up producing an element of order 6 (perhaps by looking at the product $HK$ for some suitable $K$), but I am not sure about that.
Alternatively, one can argue by contradiction.
So suppose there is a $g\in G$ with the property $g^{n!}\notin H$.
Then neither of the elements $g,g^{2},...,g^{n}$ can belong to $H$. This implies that $$H, Hg, Hg^{2},...,Hg^{n}$$ are distinct Right-cosets. But this violates the assumption $[G:H]=n$.
Best Answer
Finding subgroups of $S_n$ isomorphic to $G$ is the same thing as finding injective homomorphisms from $G$ to $S_n$.
Finding homomorphisms from $G$ to $S_n$ is the same as choosing conjugacy classes of subgroups $H_i$ of $G$ so that $n = \sum [G:H_i]$. The kernel of the homomorphisms is the intersection of the conjugates of all of the $H_i$.
If $G=H\times K$, then take $H_1 = H \times 1$ and $H_2 = 1 \times K$, and we get $H_1 \cap H_2 = 1 \times 1$, so the homomorphism defined by $\{H_1, H_2\}$ is injective, and $G$ is a subgroup of $S_n$ for $n = [G:H_1] + [G:H_2] = |K| + |H|$.
Repeating this with 3 groups shows that $C_2 \times C_2 \times C_2$ is isomorphic to a subgroup $S_6$ since $6=2+2+2$. By considering a Sylow 2-subgroup of $S_5$, one can see that $6$ is in fact the smallest possible $n$. An explicit subgroup is $\langle (1,2) \rangle \times \langle (3,4) \rangle \times \langle (5,6) \rangle$.
Similarly $S_3 \times S_3$ is isomorphic to a subgroup of $S_6$ since $6=3+3$. It is not isomorphic to a subgroup of any smaller $S_n$ since $S_5$'s order is not divisible by 36. An explicit subgroup is $\langle (1,2), (1,2,3) \rangle \times \langle (4,5),(4,5,6) \rangle$.
$Z_9$ is isomorphic to a subgroup of $S_9$, and by checking a Sylow 3-subgroup of $S_8$, one can see no smaller $n$ will work. An explicit subgroup is $\langle (1,2,3,4,5,6,7,8,9) \rangle$.
See https://mathoverflow.net/questions/48928/smallest-n-for-which-g-embeds-in-s-n for some higher level ideas.