It does depend on what type of show it is. I've shadowed on both touring broadway shows and local shows.
For a touring broadway show, what I've done is to find out what city the tour is in right before it comes to your city. Then send a letter adressed to "The Stage Manager, c/o The ______ Tour" and the address of the theatre (which you can find on the theatre's website). In the letter, ask if it would be possible to shadow, and specify that you want to do it while the tour is in your city. And be sure to give your e-mail address. That provides a faster and more convienent way for them to get back to you. It's much easier to work out dates that are convienent for both of you that way. And if the show has a longer stay, as many of the tours do, the SM might ask you to give them some dates when you are available.
If it's production that is local, I'd say ask at least 2 weeks before, but not more than 2 months in advance.