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

Edit the file /etc/postgresql/8.4/main/pg_hba.conf and replace ident or peer by either md5 or trust, depending on whether you want it to ask for a password on your own computer or not. Then reload the configuration file with:

/etc/init.d/postgresql reload

You're getting this error because you're failing client authentication. Based on the error message, you probably have the default postgres configuration, which sets client authentication method to "IDENT" for all PostgreSQL connections.

You should definitely read section 19.1 Client Authentication in the PostgreSQL manual to better understand the authentication settings available (for each record in pg_hba.conf), but here is the relevant snippet to help with the problem you're having (from the version 9.5 manual):

trust

Allow the connection unconditionally. This method allows anyone that can connect to the PostgreSQL database server to login as any PostgreSQL user they wish, without the need for a password or any other authentication. See Section 19.3.1 for details.

reject

Reject the connection unconditionally. This is useful for "filtering out" certain hosts from a group, for example a reject line could block a specific host from connecting, while a later line allows the remaining hosts in a specific network to connect.

md5

Require the client to supply a double-MD5-hashed password for authentication. See Section 19.3.2 for details.

password

Require the client to supply an unencrypted password for authentication. Since the password is sent in clear text over the network, this should not be used on untrusted networks. See Section 19.3.2 for details.

gss

Use GSSAPI to authenticate the user. This is only available for TCP/IP connections. See Section 19.3.3 for details.

sspi

Use SSPI to authenticate the user. This is only available on Windows. See Section 19.3.4 for details.

ident

Obtain the operating system user name of the client by contacting the ident server on the client and check if it matches the requested database user name. Ident authentication can only be used on TCP/IP connections. When specified for local connections, peer authentication will be used instead. See Section 19.3.5 for details.

peer

Obtain the client's operating system user name from the operating system and check if it matches the requested database user name. This is only available for local connections. See Section 19.3.6 for details.

ldap

Authenticate using an LDAP server. See Section 19.3.7 for details.

radius

Authenticate using a RADIUS server. See Section 19.3.8 for details.

cert

Authenticate using SSL client certificates. See Section 19.3.9 for details.

pam

Authenticate using the Pluggable Authentication Modules (PAM) service provided by the operating system. See Section 19.3.10 for details.

So ... to solve the problem you're experiencing, you could do one of the following:

1. Change the authentication method(s) defined in your pg_hba.conf file to trust, md5, or password (depending on your security and simplicity needs) for the local connection records you have defined in there.

2. Update pg_ident.conf to map your operating system users to PostgreSQL users and grant them the corresponding access privileges, depending on your needs.

3. Leave the IDENT settings alone and create users in your database for each operating system user that you want to grant access to. If a user is already authenticated by the OS and logged in, PostgreSQL won't require further authentication and will grant access to that user based on whatever privileges (roles) are assigned to it in the database. This is the default configuration.

Note: The location of pg_hba.conf and pg_ident.conf is OS dependent.

Simply adding the -h localhost bit was all mine required to work

In case none of the above works for you:

I've done quite a few Postgres installations, but was flummoxed today on a RedHat 6.5 system (installing Postgres 9.3). My typical hba.conf configuration that Aron shows above didn't work. It turned out that my system was using IPV6, and ignoring the IPV4 configuration. Adding the line:

host    all             all             ::1/128                 password

allowed me to login successfully.

You can set the environment variable PGHOST=localhost:

$ psql -U db_user db_name
psql: FATAL:  Peer authentication failed for user "db_user"

$ export PGHOST=localhost
$ psql -U db_user db_name

Password for user mfonline:

Hmmm ...

If you can connect with the username and password in pgAdminIII but you can't connect with psql then those two programs are probably connecting to the database differently.

[If you're connecting to different databases, first try connecting to the same database. See below.]

From PostgreSQL: Documentation: 9.3: psql:

If you omit the host name, psql will connect via a Unix-domain socket to a server on the local host, or via TCP/IP to localhost on machines that don't have Unix-domain sockets.

If you're not running something like psql ... -h host_name ..., and you're running Ubuntu, psql should be connecting via a Unix-domain socket, so PostgreSQL probably isn't configured to allow one of the password authentication methods for the postgres user.

You can test this by running:

sudo -u postgres psql

If the above works, your server is probably configured to use peer authentication for local connections by the postgres user, i.e. asking the OS for your user name to confirm that you're postgres.

So It's Probably Your pg_hba.conf File

The full path of the file will be something like /etc/postgresql/9.3/main/pg_hba.conf. You can view it by, e.g. sudo cat /etc/postgresql/9.3/main/pg_hba.conf | more.

If you're omitting the host name in your psql command, you should be able to connect if you add the following entry to your pg_hba.conf file:

# Connection type   Database   User       IP addresses   Method
local               all        postgres                  md5

[Commented lines in the pg_hba.conf file start with #.]

If you are including the host name in your psql command, add this entry instead:

# Connection type   Database   User       IP addresses   Method
host                all        postgres   127.0.0.1/32   md5

You need to put the entry before any other entries are matched for your connection via psql. If in doubt about where to put it, just put it before the first un-commented line.

More about pg_hba.conf

From PostgreSQL: Documentation: 9.3: The pg_hba.conf File [bold emphasis mine]:

The first record with a matching connection type, client address, requested database, and user name is used to perform authentication. There is no "fall-through" or "backup": if one record is chosen and the authentication fails, subsequent records are not considered. If no record matches, access is denied.

Note that records are not matched on authentication method. So, if your pg_hba.conf file contains the following entry:

# Connection type   Database   User       IP addresses   Method
local               all        postgres                  peer

Then you won't be able to connect via:

psql -u postgres

Unless one of these entries is in your pg_hba.conf file above the former entry:

# Connection type   Database   User       IP addresses   Method
local               all        postgres                  md5
local               all        postgres                  password   # Unencrypted!
local               all        all                       md5
local               all        all                       password   # Unencrypted!

Out of all the answers above nothing worked for me. I had to manually change the users password in the database and it suddenly worked.

psql -U postgres -d postgres -c "alter user produser with password 'produser';"

I used the following settings: