The problem can also be attributed to a crashed process that left postmaster.pid file behind.
$ brew services stop postgresql
# adjust path accordingly to your install, e.g. `/opt/homebrew/var/postgres/postmaster.pid`
$ rm /usr/local/var/postgres/postmaster.pid
$ brew services start postgresql
postgres has no password after an automated install, it's expected to authenticate through the peer method. sudo su - postgres is the first step to it. The second step is to connect through the Unix local domain socket, but your command doesn't do that, it connects through TCP, that's why you're stuck with the password problem.
The installed pg_hba.conf file probably starts with these two rules, apart from comments:
# Database administrative login by Unix domain socket
local all postgres peer
# IPv4 local connections:
host all all 127.0.0.1/32 md5
[...]
When doing a TCP connection with -h localhost... the first rule doesn't match. The second rule matches and it triggers the demand for a password, but as none was set this can only fail (empty passwords are not allowed either).
The solution is to remove -h localhost from psql invocation, for the first rule to be taken instead. As it's on a Unix system, it will attempt a connection through the Unix domain socket.
Once logged to psql as the postgres user, you may set a password with the \password command or ALTER USER postgres PASSWORD 'foobar';
See also https://help.ubuntu.com/community/PostgreSQL
In the section Using pgAdmin III GUI , they suggest to change the pg_hba.conf first rule from auth peer to md5, after having set a password. Personally I don't quite get why. I'd rather leave that rule alone and run pgAdmin from my own Unix account, choosing localhost TCP connections.
Best Answer
The problem is that the needed contrib files are not installed. This was actually the case for several contrib modules.
I found help with the solution to this here:
https://wiki-bsse.ethz.ch/display/ITDOC/Get+PostgreSQL+contrib+modules+on+Mac+OS+X
I suspect reinstalling everything would work too, but this highlights the actual problem.