How do I tell Prince to put page numbers in the output?

You can use CSS like this:

@page {
    @bottom { content: counter(page) }
}