Dependiendo del grado de personalización que quieres puedes usar diferentes métodos. Si es solo CSS, basta con usar el style.css.
Para cambios más profundos puedes crear una plantilla /tu-tema/woocommerce/taxonomy-product_cat.php que sustituirá a la de WooCommerce.
https://docs.woothemes.com/document/template-structure/