I'm not sure if any of the tutorial videos for UC cover taxonomy, to tell you the truth - but the fact that you'd be using it with a cart system, let alone Ubercart, is inconsequential. You can use Taxonomy with any node type, which is what makes it so powerful.

The main thing is to create the vocab in Taxonomy. Download that module and read its documentation - it'll help you understand more. You can create a single hierarchy such as what you described, or you can create a multi-tier hierarchy where products belong to multiple categories or subcats.

The only issue I'm aware of, though, seems to be with the Pathauto module generating aliases for every term or vocabulary; currently it seems to only create an alias for the first category ... but I haven't had time to test this myself.

Since Taxonomy is the main thing you need here, I would try to tinker with it and familiarize yourself first. If you still need help be sure to post back