First of all, congratulations on the acceptance!
Second, I think re-sending a puzzle is a rare occurrence. I didn't have to resend my puzzle he recently accepted. But I think I've heard of other cases of that.
Third, don't worry about the puzzle getting lost in the mail. After two weeks or so, go ahead and e-mail Will about the puzzle (OK because it was accepted). If for some strange reason he didn't get it (he's gotten every puzzle I've sent so far), go ahead and re-send.
Fourth, the next step. Well, I'm still waiting to have my first published, so not sure what the next step is. But I'm pretty sure the NYT will walk you through it. You've been accepted. Relax.