Taxonomy Hierarchy

Looking at a dump of the Grav variable taxonomy and reading through the source code, it appears that there is no concept of taxonomy hierarchy in Grav. That is if a blog is using categories and tags, there doesn't seem to be a data structure that keeps track of which tags are used by which categories. So, if you want to create a menu with the categories as the first level and the tags used in each category in the second, there isn't anything at hand to use.

Does that mean a plug-in would have to traverse the entire site to assemble such an array?

Yes taxonomies are simple independent arrays. If you want something more complex you can build it as a plugin.

Is there a built-in Grav mechanism to traverse the site's pages and query the taxonomy assign to each? Or would that be custom, too?

There are events that are fired while Twig is traversing all the pages:

page-event-hooks

Take a look at the RelatedPages plugin. I think this is a good example of building up some other logic (related pages in this case) and caching those results (for performance) during the page processing within Grav.