It is difficult to find this number for arbitrary finite groups, but many families have been solved. A somewhat early paper that has motivated a lot of work in this area is:
Johnson, D. L. "Minimal permutation representations of finite groups."
Amer. J. Math. 93 (1971), 857-866. MR 316540 DOI: 10.2307/2373739.
This paper classifies those groups for which the regular permutation representation is the minimal faithful permutation representation (cyclic of prime power order, K4, or generalized quaternion) and some results on nilpotent groups (improved in later papers).
The minimal permutation degrees of the finite simple groups are known from:
Cooperstein, Bruce N. "Minimal degree for a permutation representation of a classical group."
Israel J. Math. 30 (1978), no. 3, 213-235. MR 506701 DOI: 10.1007/BF02761072.
This paper only finds the degrees. A fuller description of the permutation representations are given in:
Grechkoseeva, M. A. "On minimal permutation representations of classical simple groups." Siberian Math. J. 44 (2003), no. 3, 443-462 MR 1984704 DOI: 10.1023/A:1023860730624.
There are a great deal of topics associated with minimal permutation degrees. I'll just briefly sketch them below, let me know if any interest you and I can give citations or longer descriptions:
The minimal degree of a subgroup is never larger than the minimal degree of the parent group, but the minimal degree of a quotient group may be much, much larger than that of the original. This poses problems in computational group theory, since quotient groups may be difficult to represent. Some quotients are easy to represent, and this has had a significant impact on CGT in the last 10 years or so.
Finding minimal permutation representations of covering groups can be difficult, and here I think the results are much less complete. Basically what you want are large subgroups not containing normal subgroups. In a covering group Z(G) is contained in really quite a few of the "good choices". This is because it is contained in Φ(G), the Frattini subgroup, the intersection of the maximal subgroups. One has to give up using maximal subgroups (at least if Z(G) is cyclic of prime power order), and so the minimal degree can increase dramatically.
Minimal degrees of primitive permutation groups is a topic with a different flavor (rather than specific families of groups, it is more of the interactions between group properties), but a great deal is known. Similar techniques are used to describe asymptotic behavior of minimal degrees of arbitrary families of finite groups, and quite powerful results are available there.
It's well-known that for a natural number $n$ with prime factorization
$n=\prod_i p_i^{r_i}$, all groups of order $n$ are abelian if and only if
all $r_i\le 2$ and
$\gcd(n,\Phi(n))=1$ where $\Phi(n)=\prod_i (p_i^{r_i}-1)$.
(See http://groups.google.co.uk/group/sci.math/msg/215efc43ebb659c5?hl=en)
For other $n$ there are non-abelian groups. If some $r_i\ge3$
then we can take a direct product of a non-abelian group of order $p_i^3$ and
a cyclic group. There are always non-abelian groups of order $p^3$;
when $p=2$ take the quaternion group, and when $p$ is odd the group
of upper triangular matrices with unit diagonal over $\mathbb{F}_p$.
Otherwise $G$ will have a factor $pq$ with $p\mid(q-1)$ or $pq^2$ with
$p\mid(q^2-1)$. In the first case the group of all maps $x\mapsto ax+b$
for $a$, $b$, $x\in\mathbb{F}_q$ and $a\ne 0$ has a non-abelian subgroup
of order $pq$. In the second case replace $\mathbb{F}_q$
by $\mathbb{F}_{q^2}$ and then get a non-abelian group of order $pq^2$.
In both cases multiply by a cyclic group to get an order $n$ non-abelian group.
Best Answer
By a Theorem of Guralnick and Lucchini (which does require CFSG), if each Sylow subgroup of $G$ (ranging over all primes) can be generated by $r$ or fewer elements, then $G$ can be generated by $r+1$ or fewer elements. As noted in comments, if $G$ has a Sylow $p$-subgroup $P$ of order $p^{a}$, then $P$ can be generated by $a$ or fewer elements (and $a$ are needed if and only if $P$ is elementary Abelian). Hence if $|G|$ has prime factorization $p_{1}^{a_{1}}p_{2}^{a_{2}} \ldots p_{r}^{a_{r}}$ with the $p_{i}$ distinct primes, and the $a_{i}$ positive integers, then $G$ can be generated by $1 + {\rm max}(a_{i})$ or fewer elements.
(The result attributed to Guralnick and Lucchini was not a joint paper, rather a result proved independently at around the same time: references:
R. Guralnick, "A bound for the number of generators of a finite group, Arch. Math. 53 (1989), 521-523.
A Lucchini: "A bound on the number of generators of a finite group", Arch. Math 53, (1989), 313-317).