Add Link Category on Activation?

Link category is a simple taxonomy just like categories , named: link_category so to add one you can use wp_insert_term() eg:

wp_insert_term(
  'My link category', // the term 
  'link_category', // the taxonomy
  array(
    'description'=> 'this is a description.',
    'slug' => 'my-link-category'
  )
);

and to make all this happen on plugin activation take a look at register_activation_hook