Setting up catalog taxonomy
Your first assumption was right. The taxonomy items should be for categories and the products should be nodes to type product. 

It looks like this is not as simple to setup for D6 where you could use 

[term-raw]/[title-raw]


This comment on drupal.org has some helpful suggestions


Download Entity API
enable entity and entity tokens
Setup a path something like [node:field-category:name]/[node:title]