Adding a category to a profile adds the profile to the category. :) So you would do that if you want the profile to actually appear on the category page. This is almost always what you want.
Linking to a category is more for if you're talking about a category. You don't want the profile you're editing to be in the category, but you want to refer to it. For example, on the Canada category there's a link to Category:United States of America, where it says that Canada and the US share a border. Canada doesn't belong in the US category; it's just a link so that people can navigate there.
I hope that helps!