While a PLAN is being created by the BIND process, normally the STATISTICS of the Tablespace is used. That is why the utility RUNSTATS is very important to BIND process. When you run a REORG and LOAD utility on a tablespace, it is advised to run REBUILD and RUNSTATS utility. After that REBIND the PLAN which will give you the new access path based on the new statistics of your tablespace.
For the second part your query
When an SQL is executed - Static or Dynamic - there must a PLAN to access the table. If it is a Static SQL, there must a predefined PLAN. Because we have to BIND the plan before the execution.
If the SQL is a Dynamic, before accessing the table for rows, BIND process will go through these steps.
1. Check the syntax.
2. Resolves the table name
3. Check the privilege
4. Create access path based on statistics
5. Reserve the resource
6. Execute the SQL.
7. Send the result to the desired location.
For your third part of your query
The PLAN is neither stored in DB2 Catalog nor in the Database.
PLAN is stored in the DB2 Directory- DSNDB01.
Please go through as many as DB2 manuals as possible.