Where are hooks stored/cached?
The hook implementations ARE cached inside the database.. this is why it's necessary to clear cache in order for a newly implemented hook to fire.

Taking a look, inside the cache_bootstrap table, there is a row with cid value of module_implements, and it's data value is a very large serialized string.  When unserialized, it is an array of the form


  'hook_name' => array('module1', 'module2', 'module3', ...)


The hook names have the hook_ beginning lopped off, so hook_block_info() will appear as block_info. I believe the value is the list of modules which implement that hook, so...


  'block_info' => array('views', 'webform', 'my_module')


Means that the following hooks are registered and should be fired:

views_block_info()
webform_block_info()
my_module_block_info()