Dustin, if you know the character $\chi$ of a representation $\rho$ of a finite group, it is easy to see whether it is faithful or not.
Your representation is faithful if and only if for every $g \in G$, $\chi(g)=\chi(e)$ implies $g=e$. For if $g \in G$, and $\chi(e)=n$ is the dimension of your representation $\rho$, $\chi(g)$ is the sum of the $n$ eigenvalues of $\rho(g)$, which are roots of unity, hence $|\chi(g)| \leq n$ with equality if and only if all eigenvalues are the same, that is if and only if $\rho(g)$ is scalar, and then $\chi(g)=n$ if and only if $\rho(g)=1$.
So each time you have a table of characters for a group, you know which of its irreducible
representations is faithful, and you can easily find the one of smallest dimension.
You can find tables of characters in many places, like in the atlas of finite groups already mentioned for certain groups (apparently close to simple groups, so not the one for which your question is the most interesting), or for some noteworthy groups on wikipedia, or on sage by typing G.table_of_characters() if G is your group, etc...
Now as Derek said in comments, that doesn't really answer your initial question of finding
the faithful representation of smallest dimension, which may not be irreducible. For this
you just have to test with the above criterion the various sums (with repetitions)
of irreducible characters, by increasing order of dimension, until you find one
that is faithful, which in general should to take too long. This would be easy to program in sage, say...
This is a naive approach of a non-specialist. It is very possible that there are more clever ways to find the smallest dimension of a faithful representation. This suggests many questions -- What can be said about groups such that there smallest faithful representation is irreducible, for instance ? Or, what is the dimension of the smallest faithful representation of, say, $GL_2(\mathbb Z/\ell^n \mathbb Z)$ when $\ell$ is a fixed prime and $n$ varies?
In this instance the table of characters has been recently determined, but it is quite complicated and the naive method suggested above seems impractical.
Best Answer
I haven't heard this question before, but I would approach it in a following way: you know some basic relations between irreducible representations of a groups — e.g. their
#is the#of conjugacy classes — and let's say we've written the kernels of representations and their dimensions. The generating function(*)that counts all representations is $((1-x^{r\_1})(1-x^{r\_2})\dots (1-x^{r\_k}))^{-1}$ and you're asked to subtract the representations that have nontrivial kernel. This combinatorial problem is partly tractable for a given group, though I don't see a nice closed formula.The situation simplifies for Abelian groups, and the answer you provide is in the right direction. A semisimple representation of Abelian group is a sum of characters. (I misunderstood what you asked here a bit, but bear with me.) A single character could already be faithful: for example, for $\mathbb Z\_2 \times \mathbb Z\_3 = \mathbb Z\_6$ the irreducible character that hits all 6-roots of unity is a faithful representation. And there are $\varphi(6) = \varphi(3)\cdot\varphi(2) = 2$ of those. Another example: $\mathbb Z\_2\times \mathbb Z\_2$. The same formula doesn't works here as $1\cdot 1 = 1$ but the corresponding representation isn't faithful. For two-dimensional case, you positively get two characters, but there is no reason to expect that there will be a splitting into a character of exactly first summand and exactly second summand. You should, however, be able to calculate it by the method below.
So the formula $\prod\varphi(m\_i)$ will correctly describe the answer only for a case of group having only one invariant factor.
Here's how to make a complete computation for an $n$-dimensional space and the case of $\mathbb Z\_6$. You need to take all representations of it which are neither representations of $\mathbb Z\_2$ nor of $\mathbb Z\_3$. Fortunately, this is easy to write using inclusion-exclusion principle: $(1 -x)^{-5} - (1-x)^{-1} - (1-x)^{-2} + 1$ and you can simplify this or just get the first three terms:
$1+5x+20x^2 + 5x^2 - 1 - x - x^2 - 1 - 2x - 3x^2 + 1 = 0 + 2x + 21x^2 + \dots$ The 2 here stands for 2 "simple" characters of $\mathbb Z\_6$, while 21, if I made no mistake, is the number of 2-dimensional representations: 19 of them are of the type "character as above $\oplus$ anything" and 2 of the type "character of $\mathbb Z\_2$ $\oplus$ character of $\mathbb Z\_3$ ".
Now I think using the same principle you can actually write a generating function for your sequence with an inclusion-exclusion principle for any group G. Since a representation is faithful iff it doesn't have a kernel, you can enumerate all of your normal subgroups and then find your answer as $F\_G(x) - F\_{G/H\_1}(x) - F\_{G/H\_2}(x) - \dots + F\_{G/H\_1\cup H\_2}(x) + \dots $. Here the notation $F\_G(x)$ is a generating function counting all representations and $H\_1, H\_2, \dots$ are all maximal normal subgroups.
Hope that helps.
Update: I understand now you're interested in a closed formula for a specific case. For example, the computation by the formula above for $\mathbb Z\_2\times \mathbb Z\_2$ gives $(3\cdot 4)/2 -1 -1 -1 = 3$. The normal subgroups of an Abelian group are not hard to write, so it would be plausible if this could be made into a good formula.
(*)Let me know if you're not familiar with generating functions.