There are two factors:
- looking for a university and a research group,
- having time for the formal admission process.
I will start for the later, as it is simpler. It depends on place, but some typical estimates of effective time you need are (at least, for applicants from aboard):
- in US ~1.5 year,
- applications for Oct in Dec-Jan plus SATs that need to be taken before,
- in UK ~1 year,
- applications for Oct in Dec-Jan,
- in continental Europe ~3 months,
- some applications May-Jun, some - on rolling basis.
However, it depends to some degree on particular university or institute (so always check that; and also check prerequisites, e.g. language tests, documents to be collected - some of them need time).
Moreover, it depends also or your national/visa status.
When it comes to searching for a group, it varies. You may find an advisor of your dreams on the first conference you attend (or via a talk at your university, or recommendation of a local professor), or you may spend a year and be far from that. (See also: Methods for finding graduate programs for specific areas of research.) The time you need depends on:
- popularity of your target field,
- how well are you networked in the target field,
- how popular is your current universities for that field (are professors well networked? are there many talks of invited guests?),
- how many conferences/schools/workshops you attend and how good are you at networking.