Theming views page and pagination
You have to be a bit more concrete when you ask for how to theme a view. One thing to note is that views help you with template suggestions (names for templates) which is one of the most common and easiest ways to alter the output of Views.

Pagination can be setup from within the interfacer. There is a pager link you can click on to set that up, if you look around a bit I'm sure you'll find it. The location depends on the Views version you use.