How to theme a view with Zen?
When you go to the view, open the advanced section - near the bottom is a link called theme: information.

This lists all the potential files you COULD adjust to tweak the output of the view. Some are very generic, and some specific to the view you are looking at - in general if you only want to theme the one view, choose a file name with your specific view name in it.
Exactly which file(s) need to adjusted depends on the kind of tweaking you want to accomplish.
These files (i.e. views-view-profile--page.tpl.php ) would then be placed in the theme directory (i.e. /sites/all/themes/zen) unless the theme uses a sub-directory for template files - a simple look through should tell you where they are found for each theme.