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.
Also, this feature will only work properly with Drupal 6.3 and later; prior to Drupal 6.3 this patch will be required.