Where does an execution plan come from? Is there a way I can determine if a plan was just generated for a particular query, or was found in the plan cache?
SQL Server 2012 has an indicator in the plan itself, RetrievedFromCache, which can be either "true" or "false".

This appears to be the property you are asking about.

This is a sample (the last line shows the property):

&lt;StmtSimple StatementCompId="1" StatementEstRows="1" StatementId="1" 
StatementOptmLevel="FULL" StatementOptmEarlyAbortReason="GoodEnoughPlanFound" 
StatementSubTreeCost="0.0508992" StatementText="SELECT COUNT(*) 
&amp;#xD;&amp;#xA;FROM sys.tables" StatementType="SELECT" 
QueryHash="0x9A4B63A948B30EA0" QueryPlanHash="0xF357CAE882D5B15D" 
RetrievedFromCache="true"&gt;


Unfortunately, I do not see anything similar in a plan generated by SQL Server 2008 R2.

In SQL Server 2008 R2, you can use the sys.dm_exec_query_stats system DMV to inspect the creation_time column for plans that have the same query_hash value.  The query hash can be obtained from the header of the plan XML (see the example above).  This query will return rows regarding the plan mentioned above:

SELECT *
FROM sys.dm_exec_query_stats qs
WHERE qs.query_hash = 0x9A4B63A948B30EA0;