I created a view which is viewable at
http://mysite.com/branch-locator. The view is being displayed by my page.tpl.php. How do I override this and use a new template file called branchlocator.tpl.php to display my view?
How specific do you need to be with the name of your template file? You should be able to create a page--branch-locator.tpl.php that gets picked up by Drupal's auto-detection mechanism. At least, that would have worked in D6 (minus the extra hyphen after page).