The following steps work for a fresh install of postgres 9.1 on Ubuntu 12.04. (Worked for postgres 9.3.9 on Ubuntu 14.04 too.)
By default, postgres creates a user named ‘postgres’. We log in as her, and give her a password.
$ sudo -u postgres psql
\password
Enter password: ...
...
Logout of psql by typing \q or ctrl+d. Then we connect as ‘postgres’. The -h localhost part is important: it tells the psql client that we wish to connect using a TCP connection (which is configured to use password authentication), and not by a PEER connection (which does not care about the password).
$ psql -U postgres -h localhost