How early should a graduate student begin their job search? Generally speaking, are there good "milestones" to suggest that a graduate student should initiate their job search? Roughly a year from completion? More? Less? Is there a particular time of year a job search should be kicked off?

Basically: The job search, how do I time it?
The following is condensed from advice for academic job hunts that I've read here and here - I imagine it should be somewhat applicable for jobs in industry as well:


If you would be applying for a position at Fall, begin applying from summer the previous year - applications tend to be sorted during committee meets, and the earlier you apply, the fewer applications are there, so there are higher chances of getting your application noticed. Hence, you'll want to draft your research statement, teaching statement and curriculum vitæ (CV) the summer before your search. If you are applying for industrial as well as academic positions, you probably want more than one resume, since achievement, skills, and goal-oriented resumes can be more effective in the industrial setting. 
The middle of January is when most schools stop accepting applications. Even then, keep submitting to any position you find through February, particularly if someone there recommends you apply. You will probably hear back with invitations for interviews in January and February, but sometimes even March and April. 
Get your letter writers primed as early as possible. You'll need at most six letter writers, but no less than three, and you'll want to ask them at least a month in advance with all your documents.