Which file do I need to edit to implement a 'Back to top' link? I am running a Drupal 6.22 site, with a custom template installed in /sites/all/themes/mytheme. Which template file should I edit to implement a back to top link?
It depends where you want the link to be, but your best bets would probably be page.tpl.php, node.tpl.php or a variation of those templates (specific to content types, etc).

For more on templates see Drupal 6 template suggestions