PostgreSQL error when trying to create an extension

The following will get you a working postgis install on Ubuntu 12.04 (Note: also tested on 13.10)

echo "deb http://apt.postgresql.org/pub/repos/apt/ precise-pgdg main" | sudo tee /etc/apt/sources.list.d/postgis.list
wget --quiet -O - http://apt.postgresql.org/pub/repos/apt/ACCC4CF8.asc | sudo apt-key add -
sudo apt-get update
sudo apt-get install postgresql-9.3 postgresql-9.3-postgis-2.1 postgresql-client-9.3
sudo -u postgres psql -c 'create extension postgis;'

Based on the docs at https://wiki.postgresql.org/wiki/Apt

You need to install postgresql-9.1-postgis-scripts. In Ubuntu or Debian, you need to run the following command as root:

apt-get install postgresql-9.1-postgis-scripts

This adds the files needed to create the postgis extensions.

Installing this package did the trick for me on my Linux Mint 16 box:

# install hstore postgresql extension.
sudo apt-get install postgresql-contrib

Daniel Vérité is close to the truth, but not enough. The package missing is postgresql-9.1-postgis-2.0:

sudo apt-get install postgresql-9.1-postgis-2.0