This screencast shows an example of the special case of theming Views. This does, in general, work as theming other parts of Drupal – you copy template files to you theme and modify them, you write preprocess functions, and you write theme functions. But when it comes to finding template suggestions files for making specific overrides, Theme Developer isn't very good at doing that. Instead, you'll have to go into Views and click the "theme: information" link, right at the bottom of the advanced section. That will give you a list of the template files you can use to make specific overrides.
If you're theming for a theme that is not used by default on the site, make sure to use the option to switch theme for template detection.