How can I check if a package is installed (no superuser privileges)?

apt-cache policy <package name>

I always just use this from the command line:

dpkg -l | grep mysql

so the above asks dpkg to list all the installed packages and then I grep for only those that have mysql in the name.

One more variant, using aptitude this time:

aptitude show <package>

Tab completion works here as well.