In Catalog -> Products, use Search Product to locate your product. And then click "Edit" button to start editing the product. Click "Categories" tab. In the drop down list find the new category and click "Add" button. Click "Delete" button on the right side of the category that you wish to remove. After you are done, click "Update" button.