Which PHP file would a custom theme_link function go into?
theme_link() doesn't use a template file. You can override its output by placing your own theme function in your theme's template.php file: 

function MYTHEME_link($variables) {
  //Alter this as you see fit
  return '&lt;a href="' . check_plain(url($variables ['path'], $variables ['options'])) . '"' . drupal_attributes($variables ['options']['attributes']) . '&gt;' . ($variables ['options']['html'] ? $variables ['text'] : check_plain($variables ['text'])) . '&lt;/a&gt;';
}