Finding the minimal $n$ such that a given finite group $G$ is a subgroup of $S_n$
This is not easy for general $G$, but we can immediately produce some crude bounds (on the minimal number $\mu(G)$ such that $G$ embeds into $S_{\mu(G)}$):
If we have an embedding $G \hookrightarrow S_n$, we must trivially have $|G| \leq |S_n| = n!$. Of course, this is sharp in the sense that equality holds for $G = S_n$. On the other hand, the regular representation of $G$ determines an embedding $G \hookrightarrow S_{|G|}$, so $\mu(G) \leq |G|$. This latter bound is sharp:
Theorem If $G$ is a group for which there is no embedding $G \hookrightarrow S_n$ for any $n < |G|$, then $G$ is
- a cyclic group $\Bbb Z_{p^m}$ of prime power order,
- a generalized quaternion $2$-group, or
- the Klein 4-group $\Bbb Z_2 \times \Bbb Z_2$.
There are numerous results available for certain classes of $G$. For example, if $\gcd(|G_1|, |G_2|) = 1$, then $\mu(G_1 \times G_2) = \mu(G_1) + \mu(G_2)$.This and (1) above together resolve the problem for abelian groups:
Theorem If $G$ is abelian, so that we can write it as $\Bbb Z_{a_1} \times \cdots \times \Bbb Z_{a_r}$ for (nontrivial) prime powers $a_1, \ldots, a_r$, then $$\mu(G) = a_1 + \cdots + a_r .$$
(Both of the Theorems here are given by D.L. Johnson and recorded in the reference below, which itself contains a bibliography of this topic.)
The realization of $D_8$ as the group of symmetries of the square determines an embedding $D_8 \hookrightarrow S_4$, and it's not too hard to prove that $\mu(D_{2n}) = \mu(\Bbb Z_n)$ and $\mu(A_n) = n$ (both for $n > 2$). These facts together determine $\mu(G)$ for all $G$ of order $<16$ except $Q_{12} \cong \Bbb Z_3 \rtimes \Bbb Z_4$:
- $S_1$: $\{ e \}$
- $S_2$: $\Bbb Z_2$
- $S_3$: $\Bbb Z_3$, $S_3$
- $S_4$: $\Bbb Z_4$, $\Bbb Z_2 \times \Bbb Z_2$, $D_8$, $A_4$
- $S_5$: $\Bbb Z_5$, $\Bbb Z_6$, $D_{10}$
- $S_6$: $\Bbb Z_4 \times \Bbb Z_2$, $\Bbb Z_2 \times \Bbb Z_2 \times \Bbb Z_2$, $\Bbb Z_3 \times \Bbb Z_3$, $D_{12}$
- $S_7$: $\Bbb Z_7$, $\Bbb Z_{10}$, $\Bbb Z_{12}$, $\Bbb Z_2 \times \Bbb Z_6$, $D_{14}$
- $S_8$: $\Bbb Z_8$, $Q_8$, $\Bbb Z_{15}$
- $S_9$: $\Bbb Z_9$, $\Bbb Z_{14}$
- $S_{11}$: $\Bbb Z_{11}$
- $S_{13}$: $\Bbb Z_{13}$
This question gives an explicit proof that $\mu(Q_8) = 8$.
Lemiuex, Stephan R., Minimal degree of faithful permutation representations of finite groups. (1999) Master's thesis.
In general, this is not straightforward. If $G$ acts on a set $A$ of $n$ elements, you know this induces a homomorphism $\varphi : G \to S_n$ with kernel $\cap_{a \in A} \textrm{Stab}(a)$. So your problem is reduced to analyzing stabilizers.
Of course if $G$ acts on itself, say, by left multiplication, you get an embedding of $G$ into $S_{|G|}$, but this is usually not particularly helpful. Take $D_4$, the group of symmetries of a square. Since $|D_4| = 8$ we know a copy of $D_4$ lives in $S_8$, but this isn't too revealing as also $D_4 < S_4$. A more outrageous example is Cayley's theorem shows $A_5 < S_{60}$, but we know $A_5 < S_5$.
A nice example of such an embedding is as follows: suppose we want to show any simple group of order $60$ is isomorphic to $A_5$. By the Sylow theorems one can show such a group, say $G$, has a subgroup of index $5$, and then we know this induces an injective homomorphism from $G$ into $S_5$, from the claim follows.
Cayley's theorem won't always give you information about a particular group, but it can be used to prove general facts about group theory, i.e. one can reduce a general problem to a specific case concerning $S_n$. For instance, Cayley's theorem can be used to show for any group $G$ there exists a Galois extension $K$ of $\mathbb{Q}$ with a subfield $F$ such that $\textrm{Gal}(K/F) \simeq G$.
Given a finite group $G$, consider $H$ to be subgroup such that it contains no normal subgroup of $G$ and consider such $H$ of maximum possible order.
Then $G$ permutes cosets of $H$ by left multiplication, and hence gives a homomorphism from $G$ to permutation group of cosets $\{gH\colon g\in G\}$. The kernel of this homomorphism is intersection of all the conjugates of $H$; but, by our assumption, it should be trivial. Hence $G$ embeds in permutation group on $|G/H|$ letters.
This also explains why $H$ is chosen in beginning of maximum order.
This works, as it can be seen for examples in other answers.