Page number with total number of pages: Page 4 of 65

Showing the total number of pages in addition to the actual page number is straight forward using the lastpage package.

\usepackage{lastpage}

Now you can simply access the number of pages using:

\pageref{LastPage}

Note: You will have to typeset the DVI/PDF twice in order to get the number right.

Example:

\usepackage{fancyhdr, lastpage}
\pagestyle{fancy}
\fancyfoot[C]{{\thepage} of \pageref{LastPage}}
\begin{document}
...

Note: See this recent comment on how to count the number of figures within your document.