I would definitely go for Marc's approach as well, by using a lookup field for the product category.
Looking at it from a relational point of view, a product category is an entity in itself, so that should be stored in a separate table. The problem with using just the title or only a plain choice field is that it violates at least the first normal form.
You are likely going to run into problems when you don't use a lookup field. Imagine when you want to change the name of a category. In any other approach that would result in having to update multiple entries, because changes are not reflected in other records. Changes made on a looked up value however, immediately show in your products list too.
Plus, using the title field for category has the drawback of constantly having to type your category name when adding a new product, which could easily result in unexpected behaviour when making a typo.
For future expansion, say you want to store additional information about your categories, then at least the lookup-based solution already allows you to do this without any significant changes.
Also, when querying your data, I'd say lookup fields work better too, as you can at least query on an ID instead of a plain string value, one which in this case happens to be the name of the category too. Your mileage may vary here, but the ID-based solution seems a little more robust to me.
Possible minor overhead is easily outweighed by the advantages you're getting by using a lookup field.