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.
From the company's point of view there are two different recruitment scenarios.
One is simply "maintaining the workforce" to replace the inevitable losses that occur over time. These are usually entry-level positions, and the main objective is to hire the right number of people who are "good enough". The skills and qualifications required are not specific to particular jobs; the successful pool of applicants will be fitted into the overall company structure in a (hopefully fairly optimal) way. This is more common in large companies than small ones, of course.
This type of recruitment is usually done on an annual cycle, and the timing of the process matches the normal academic timetable. It would do no harm to contact the company informally to ask them when they would prefer to receive applications. There is no sense in submitting an application that will not be processed for a few months, and may "get lost during that time.
The other scenario is a vacancy targeted at filling a specific position in the company. The requirements will be focussed on that particular role (even if the statement in the job advertisement seems rather vague and generic - a company doesn't necessarily want to tell its competitors exactly who it wants to hire!) and the objective is to fill the post as quickly as is practical depending on the local norms for notice periods, etc. If you apply for that type of job, being unable to start for a long time may be sufficient to reject you however well qualified you may be.
Such jobs are often not targeted at "first-job" college applicants either, since they may be looking for specific practical experience in industry.