psql: FATAL: Ident authentication failed for user "postgres"

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

Did you set the proper settings in pg_hba.conf?

See https://ubuntu.com/server/docs/databases-postgresql how to do it.