In your view edit page, go to Advanced -> Other -> Theme: Information.
Its dialog will expose all the theme files that are called for your view.
You can use generic to very detailed theme files that will only be use for your views display.
The first file name in Display output is views-view.tpl.php. That will apply to all views and displays.
The next one in the list is views-view--[view name].tpl.php. It will only apply to your view.
It keeps drilling down until it gets as specific as possible.
views-view--[view name]--default.tpl.php is the last one in the list and only applies to the default display of the view.
Clicking the Display output: link will expose the template code that views uses.
Simply copy and create a new template file with one of the suggested in the list.
It's usually best to be as specific as possible.
The template file can go anywhere in your theme
and views will pick it up as long as you rescan template files in the theming information and save the view.
There are view templates, row templates, field templates and field specific templates.