It can be as many as several months prior -- my November release, Stargazer, is already available for pre-order on Amazon and B&N.com, and has been for about a month now. (OTOH, that's the second in a series, and maybe they put series titles up a little earlier? No idea.)
Pre-publishing sales are a good sign, naturally, although lack of pre-pub sales probably doesn't count against you to any great degree; plenty of books take a while to gain traction.