Use the Administration Tools -> Product Categories page to add, change or delete product categories.
To change the icon appearing next to each menu link, change the the following three files located in the theme folder (for example, images/site/default/)