Apparently, it is possible to search for packages with apt. Here is it works:
apt-cache search mplayer
Masks are also supported. Consider the difference (package descriptions were removed for cleaner output):
[leonid@ltsp ~]$ apt-cache search lad glade2 intltool libglade libglade libglade2 libglade2-devel pygtk2-libglade qt-designer Gtk-Perl ladspa ladspa-devel mplayer xine-lib [leonid@ltsp ~]$ apt-cache search '^lad' ladspa ladspa-devel