How does one create a RMAN recovery catalog?

Start by creating a database schema (usually called RMAN)

Assign an appropriate table space to it and grant it recovery_catalog_owner role.

sqlplus sys
SQL>create user RMAN identified by RMAN;
SQL> alter user RMAN default table space tools temporary tablespace temp;
SQL> alter user RMAN quota unlimited on tools;
SQL> grant connect, resource, recovery_catalog_owner to RMAN;

Next, log in to RMAN and create the catalog schema.

Prior to Oracle 8i this was done by running catRMAN.sql script.

RMAN> catalog RMAN/RMAN
RMAN>create catalog tablespace tools;
RMAN> exit; 

You can now continue by registering your databases in the catalog.

RMAN catalog RMAN/RMAN target backdba/backdba
RMAN> register database;