We operate a quarterly planning horizon and yet we have a very healthy order book. Detailed plans only stretch out as far as 3 months. How do I tell a customer who has just ordered when they will be likely to go live?
You use the same planning / estimating process you use to arrive at your three-month detailed plans and schedules. The steps and the inputs are exactly the same, only at a higher level of decomposition and with more uncertainty or variability built in. What you end up with is a ROM (rough order of magnitude), which has a +50%, -30% expected variance, which is also communicated to the customer. You have to be careful because even though you tell them the variance, it'll be long forgotten. So make sure you say that several times and have it part of your written estimation.
It comes down to amount of work that needs to be done on the project, divided across days available by the people who are doing the work, with a fudge factor for uncertainty/changes/risks and taking into consideration the amount of time it takes to get feedback back and forth from the customer or other people involved with the project (like 3rd party vendors).
In a more Agile approach, it is done when it is just good enough to provide the value/functions that customer is looking for.