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.

3more comments