Do all users need access to the postgres database in pg_hba.conf?
What you see is pgAdmin connecting to the configured  Maintenance DB - which is postgres by default. Select a server in the object browser pane and choose "Properties" from the context menu (right-click). The drop-down menu only offers the typical choices, but you can just type in any database name.

If a user's access is limited to one database in pg_hba.conf (which is the most efficient place to do that), you can make it work with pgAdmin by configuring this one database as maintenance db. Nothing bad will come of it.

The other option is to grant access to the maintenance DB (postgres or whatever) in pg_hba.conf additionally.

You can also open all gates in pg_hba.conf and regulate access with database permissions, like @a_horse explained in his answer. This is easier to manage, but restricting access in pg_hba.conf is safer and faster - more robust against DoS attacks and heavy load. Won't make a big difference in most cases, though.

Quoting the documentation of pgAdmin 1.22 (final release of pgAdmin III):


  The maintenance DB field is used to specify the initial database that
  pgAdmin connects to, and that will be expected to have the pgAgent
  schema and adminpack objects installed (both optional). On PostgreSQL
  8.1 and above, the maintenance DB is normally called 'postgres',
  and on earlier versions 'template1' is often used, though it is
  preferable to create a 'postgres' database for this purpose to avoid
  cluttering the template database.