Debian (and ubuntu) packages for ejabberd don’t contain drivers for mysql. If you want to connect your ejabberd to mysql you need to get those drivers separately from the external ejabberd modules repository and compile them on your own.
For convenience I’ve built a debian package containing the precompiled modules:
ejabberd-mysql-20090114_1-2_all.deb

Note: this package is not of the usual quality you’d expect from an official debian package. It’s just an alien’ed tarball containing the drivers at the right place (i.e. ‘/usr/lib/ejabberd/ebin’).