If you're talking about job searches in general, it's never too early to start making contacts with potential future employers. Getting on their "radar screen" early can only help you when it comes time to apply formally for jobs; in addition, if you are their "preferred" candidate, you may find a job posting "stressing" your particular research direction.
When it comes time for the actual submission of applications, academic positions typically operate on an annual cycle that depends on the field, and you should plan accordingly, as given in the response by shan23. The timing for other jobs varies, in particular depending upon the state of the economy. However, at the absolute minimum, you should start applying six months before your anticipated graduation; in the current circumstances, I think twelve months ' advance lead is also acceptable. Further out, the crystal ball is probably too cloudy for both employer and applicant.