I've heard conflicting advice on this, from 6 months prior to graduation all the way to "wait until after you've graduated so you can start immediately". On the one hand you don't want to give yourself too little time to interview, but on the other I understand that employers may want you to start immediately to fill a need. Is there anything rude/impolite/weird about applying for a job knowing that you won't be able to accept an offer for several months? Do companies routinely wait on Ph.D.'s to finish?
Most articles found by a search for "how long does it take to find a new job" state anywhere between 3-6 months. Anecdotally, both for myself and for my friends, this is quite accurate. This, combined with the fairly frightening statistic that unemployed people have a MUCH harder time finding employment, would lead me to strongly recommend that you start well before you graduate.
Most positions that hire PhDs are familiar with the nuances of hiring someone who hasn't yet graduated. I currently work in industry, and we've had a number of people who've had to take a few days vacation to defend their thesis. You should mention during the interview process where you currently stand in your PhD work so the employer knows what to expect, but from my experience it shouldn't be too much of a problem.
Do note that some positions require the PhD of their employees, so you would not be eligible for those types of positions until you graduate. I would still recommend interviewing anyways so you're not starting from scratch... you can just contact them and continue when you actually receive the degree.
I have been involved in hiring several Ph.D.'s (math, computer science, operations research) in the finance industry in the US. (before returning to academia to get my own math Ph.D.). In the US, the answer to your question is that the correct time to apply will depend on the type of industry job you are looking for. My experience is that for jobs at larger companies which routinely hire Ph.D.'s you should start applying in the late fall before you anticipate graduating. These companies generally have a well-developed recruitment process and are recruiting with the anticipation of bringing someone on several months down the road. They may even plan to have you start with other recent Ph.D.'s and have some more or less formal training period. (My experience is in finance where this is the norm, other industries may differ.)
For jobs at smaller companies or start-ups, I would recommend waiting. Typically these companies are looking to hire someone who can start as soon as possible (six months is an eternity for a small company or start-up).
So I would recommend starting applications and attending recruitment events for larger companies in your field right now. As the process evolves and the time until you could reasonably starts decreases, you should then expand the range of places you are talking to.
This may also vary along the size of the company and the plans that company has.
If a company wants someone just to complete a task, them maybe if you say on the interview that you will be available after three - six months then the answer will be something like that: We will contact you after this period, and believe me they never call you back. So, a good policy is to make an proposal for part time job untill you finish you Ph.D. (I know this is not easy in all times).
One other scenario:
If you apply to a big company with a long business plan then you can discuss with them when you are able to get started.
My suggestion is to start looking for a job two - three months before you finish your Ph.D.