Try using the filter_horizontal attribute on your admin class, for example:

class SomeModelAdmin(admin.ModelAdmin):
    filter_horizontal = ('users',)

As mentioned in the documentation, "adding a ManyToManyField to this list will instead use a nifty unobtrusive JavaScript "filter" interface that allows searching within the options". filter_vertical does the same thing with a slightly different layout.