To give a comparison, Empire Total War was announced September 07 or there abouts, 18 months before its release next year. Elemental was announced this month, approx 16 months before planned release date (I won't tempt fate by asking how final that date is )
As for Starcraft 2, it was announced 18 months ago and will probably be out sometime in the next century if we are being optimistic.
Basically a developer announces what they are working on around this sort of time, maybe release a mini teaser trailer showing the concept and a couple of alpha stage screenshots, and then occasionaly reminds people what the project is about over the next few months before starting proper hype etc when it's nearing completion.