Using PostgreSQL (psql) - getting past the immediate authentication failure

How in the world aren't there very clear instructions for getting started with PostgreSQL after apt-get install postgresql?

UPDATE: Doing this the right way

Read the documentation that Debian (and so Ubuntu) provide, typically in /usr/share/doc/<package-name>

The documentation we need can be read with:
vi /usr/share/doc/postgresql-8.4/README.Debian.gz

2. Get a shell for the database superuser 'postgres'. If your system
has an active root user, use su:

$ su -c "su -s /bin/sh postgres"

If your system uses sudo to get administrative rights, use sudo instead:

joe$ sudo -u postgres sh

3. In this postgres shell, create a database user with the same name as your
Unix login:

$ createuser -DRS joe

Old flailing around left for posterity

sudo vi /etc/postgresql/8.4/main/pg_hba.conf

change these two lines to:

# Database administrative login by UNIX sockets
local   all         all                          trust

# TYPE  DATABASE    USER        CIDR-ADDRESS          METHOD

# "local" is for Unix domain socket connections only
local   all         all                               trust

and:

sudo /etc/init.d/postgresql restart