I was working full-time as a lab manager whilst I completed my PhD, so I was a little slow to get started in the job hunting process. From the time I graduated to the time I received a job offer as a researcher was about 4 months (7 months after submission of my theisis). Realistically, I should be looking from about 6-12 months prior to graduation not after submitting my thesis.
My biggest tip for getting a job is network, network, network.... it is not what you know it is who you know. Sad but true. Where I come from (Australia) any university or government job over 12 months in duration has to be advertised regardless of whether there is a candidate already identified for the position. So applying through job ads can sometimes be a pointless process. You are better off approaching researcher leaders (during your last year of your PhD if possible) and talking to them about job opportunites directly. Even if there isn't one available at the time you are more likely to be remembered when positions do become available.