Is there a way to auto-paginate "Page 1 of 3" in Pages? Is there a way to auto-paginate with "1 of 3" "2 of 3" "3 of 3"?
Yes. Pages 09 certainly has this.

In the insert menu you should use both page number and page count to get page 2 of 3. You can use these anywhere, not just in the header or the footer.