1. Go to your site
2. Click on Documents and Lists at the top of the page
3. Click on Links under "Lists"
4. Click on Modify Settings and Columns (on the left)
5. Click on Link Categories under "Columns"
6. Under "Optional Settings for Column" where the other categories are listed, add your new one(s).
7. Click OK at the bottom