Is it recommended to install extensions into pg_catalog schema? Since objects in pg_catalog schema are implicitly in the search_path (docs), would it be recommended to install extensions in that schema?
Don't install extensions to pg_catalog (unless that's their default: very few extensions are designed that way), because you don't mess with system catalog, ever. @Chris demonstrates one reason why. There are others.

However, the "public" schema is in no way special. It's just the default schema that's pre-installed in standard distributions so we can get started right away. Some DB admins don't use the "public" schema at all, some even delete it.

CREATE EXTENSION is not affiliated to the "public" schema. It installs into the current schema unless instructed otherwise - except some extensions have a pre-set schema (like PGQ / Londiste). The documentation:


  schema_name
  
  The name of the schema in which to install the extension's objects,
  given that the extension allows its contents to be relocated. The
  named schema must already exist. If not specified, and the extension's
  control file does not specify a schema either, the current default
  object creation schema is used.
  
  Remember that the extension itself is not considered to be within any
  schema: extensions have unqualified names that must be unique
  database-wide. But objects belonging to the extension can be within schemas.


Bold emphasis mine.
Decide how to manage users, schemas and the search_path:


How does the search_path influence identifier resolution and the “current schema”


Then decide where to install extensions. You can install to any schema of your choice and include that schema in the default search_path for all users or just for some or no users at all (so that qualified references are required). It all depends on what you want to achieve.
Whatever you do, stay consistent.

I like to install extensions (that allow it) in a dedicated "extensions" schema, which I include in the default search_path after "public" (and "$user" - if you use that). Helps with a clean separation of my own public functions and other public objects. My setting in postgresql.conf:

search_path = "$user",public,extensions


Or:

search_path = public,extensions


And I install extensions with:

CREATE EXTENSION some_extension SCHEMA extensions;


One thing to note: This way you can "hide" (unqualified) objects in the extensions schema behind objects of the same name (and parameters) in the public schema.

Related:


Best way to install hstore on multiple schemas in a Postgres database?
How can I fake inet_client_addr() for unit tests in PostgreSQL?