First of all, congratulations Clive and Mike on being published!
I just checked: I got the acceptance e-mail for my puzzle on 30 May 2009, and the Puzzle Constructor's Agreement the next day
(1 Jun 2009)! So I'd be surprised if you didn't get it in a couple of days.
As far as when puzzles get published, I can give you a couple of examples. I know someone whose puzzle took over a year to be published. My puzzle, from the date of acceptance to appearance in the paper, took 3 1/2 months. Both of our puzzles were Sunday puzzles.
So why the big disparity (btw, they were published just a few months apart)? The one that took over a year was a fairly standard word play puzzle. My puzzle, on the other hand, was certainly unusual with that bingo "card" in the middle, so Will decided to run it quicker, even though it required more work on his part to produce.
Also, different days of the week have different sized queues. I hear the Monday queue is relatively small, and themeless puzzle days (Friday and Saturday) are rather long. The queue for diagramless puzzles is particularly long I hear.
I look forward to seeing your published puzzle(s)!