Genuine authentication failures and related problems generally manifest themselves through error messages like the following.
No pg_hba.conf entry for host 123.123.123.123, user joeblow, database testdb
This is what you are most likely to get if you succeed in contacting the server, but it does not want to talk to you. As the message suggests, the server refused the connection request because it found no authorizing entry in its pg_hba.conf configuration file.
Password authentication failed for user 'joeblow'
Messages like this indicate that you contacted the server, and it is willing to talk to you, but not until you pass the authorization method specified in the pg_hba.conf file. Check the password you are providing, or check your Kerberos or ident software if the complaint mentions one of those authentication types.
FATAL 1: user "joeblow" does not exist
The indicated user name was not found.
FATAL 1: Database "testdb" does not exist in the system catalog.
The database you are trying to connect to does not exist. Note that if you do not specify a database name, it defaults to the database user name, which may or may not be the right thing.
Note that the server log may contain more information about an authentication failure than is reported to the client. If you are confused about the reason for a failure, check the log.