You may use any of the following possible theme files to modify individual parts of your view. In total, there are four parts to theming a view.
The link to the left of each type will give you information about the default template used for that type. You may cut and paste this and place it in your theme with the appropriate template, or you may copy the base file from the views/theme directory (or, if provided by a module, from the module's directory). It is important that you clear the theme registry cache every time you add a new template, or the new template will not be picked up.
In addition to this tool, the very useful devel module contains a tool called the "Theme developer" which does a good job of visually showing you which areas of your site use which themes. Be careful with it, though, as the theme developer causes the Views edit page to break.
Also, this feature will only work properly with Drupal 6.3 and later; prior to Drupal 6.3 this patch will be required.