You should create a new category from the moment you have at least two products with equivalent attributes. Products in a category should be comparable, if not interchangeable. Keep this idea in mind when adding new products and creating new categories.
You may choose to not create any category, and have all products grouped into a single global category, "Home". But then customers won't be able to compare products. You may also decide that you are not interested in the comparison feature, and would rather build your categories freely. In that case, you should disable the comparison feature: go the product preference page, and put 0 for the "Product comparison" option.
When creating a product category, you should focus on one thing: the products in this category must be comparable through their attributes (not their features). This is not only useful for your customers, but it is also a necessity for PrestaShop's product-comparison feature.
Categories are determinant of how people will navigate on your site and search for your products. You should focus on your category tree and how categories are organized even before you start creating product sheets.