Theming views can be somewhat tricky, depending on the kind of views you have created and the changes you need to make. Check out this introduction for Views 2, and make sure to install the Advanced Help module to get at the views2 documentation from the views module itself (there will be a link to the documentation on your views overview and edit pages, once you activated the Advanced Help module).

You can also find some questions/answers here on SO (e.g. Drupal 6: How to quickly theme a view?), if you search a bit.

I actually did this the other day. Ill give you a brief overview and expand a little later.

1. Set up your view; by going to Views -> Add View
2. Once, your view is completely set up, at the bottom of the view (left column in D6, right-most "Advanced" column in D7), you will see a link called "Theme: Information", click on it.
3. What you will be presented with is a list of templates (.tpl.php) files that the views uses to theme your data. Basically the file names that are bolded are the files views is using to theme the data.

To Customize Your Views

1. Select the page you need to theme. For Example, if you created a "Block" view, and I wanted to customize the basic html layout, I would pick a name (other than the one that is currently bolded) that is being displayed to me and create the file in my themes directory (sites/all/zen/custom-file-view-fields-views.tpl.php) - this is if views told me that I could use the filename custom-file-view-fields-views.tpl.php
2. The next step is knowing what code you need to put in there. The quickest way, is to go back to the theming information in views, click on the link of the file your replacing and grab the code that is presented to you. Paste that code in the file you created.
3. From here on out, you can now successfully customize that view.

Keep in mind that the theming information presented to you is presented from basic to complex (up to down). So choose which file you need to edit carefully. Ill put up some images in this answer a little later.

Hope this helps! Cheers!

Is there something specific you re trying to accomplish? There s a lot of ways to "theme" a view, unless you mean "theme" in the strict Drupal sense.

Personally I just give the fields classes and use those, rewriting the output to include variables as classes if need be. This tends to be easier and more manageable than modifying TPL files directly.