Is there a way to auto-paginate "Page 1 of 3" in Pages?
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.