Also, depending on the repositories apt is using, you may not have the latest and greatest version of mysql installed/available on your system. debian has three main repositories: /stable, which is their current version, soon to be replaced by /testing. Finally, /unstable is full of packages that are still under development to integrate into future versions of debian.
Besides the repositories that are available from official debian mirrors, there are many, many repositories out there for backports to popular new applications, and other nifty stuff. Check out http://apt-get.org
for a very complete listing.