Today I upgraded a production PostgreSQL 8.4 database to version 9.1. This was on a Debian server. The first step is to make a full dump of your data. I personally like to store that dump somewhere safe before upgrading. As root:

su - postgres
pg_dumpall > dump.sql
exit
cp ~postgres/dump.sql /root/

Now you can safely remove the postgresql-8.4 and install postgresql-9.1:

aptitude purge postgresql-8.4
aptitude install postgresql-9.1

Next check the postgresql configuration in /etc/postgresql/9.1/main. If you make any changes, make sure to restart postgres with /etc/init.d/postgresql restart.

Postgresql 9.1 is now up and running, let's import our data back into it.

su - postgres
psql < dump.sql

That's all. You're now fully upgraded to PostgreSQL 9.1.