I know this question is old and has an accepted answer, however the question comes up among the first when searching for a PDFsharp solution. 
For the record, achieving this in PDFsharp is easy. The PdfDocument class, found under the PdfSharp.Pdf namespace contains a collection of pages (PdfDocument.Pages). All you have to do is iterate through the collection and add the page counter somewhere on every page, using a XGraphics object, that you can instantiate using XGraphics.FromPdfPage(PdfPage).
using PdfSharp.Pdf; // PdfDocument, PdfPage
using PdfSharp.Drawing; // XGraphics, XFont, XBrush, XRect
                        // XStringFormats
// Create a new PdfDocument.
PdfDocument document = new PdfDocument();
// Add five pages to the document.
for(int i = 0; i < 5; ++i)
    document.AddPage();
// Make a font and a brush to draw the page counter.
XFont font = new XFont("Verdana", 8);
XBrush brush = XBrushes.Black;
// Add the page counter.
string noPages = document.Pages.Count.ToString();
for(int i = 0; i < document.Pages.Count; ++i)
{
    PdfPage page = document.Pages[i];
    // Make a layout rectangle.
    XRect layoutRectangle = new XRect(0/*X*/, page.Height-font.Height/*Y*/, page.Width/*Width*/, font.Height/*Height*/);
    using (XGraphics gfx = XGraphics.FromPdfPage(page))
    {
        gfx.DrawString(
            "Page " + (i+1).ToString() + " of " + noPages,
            font,
            brush,
            layoutRectangle,
            XStringFormats.Center);
    }
}
It's worth noting that if a XGraphics object already exists for a given page, before creating a new one, the old one needs to be disposed. This would fail:
PdfDocument document = new PdfDocument();
PdfPage page = document.AddPage();
XGraphics gfx1 = XGraphics.FromPage(page);
XGraphics gfx2 = XGraphics.FromPage(page);