In my experiences - approximately one academic year before you graduate. Not all companies will be ready to hire at this point, but watch for companies that are recruiting at your university with information sessions, start learning about benefits, and reach out to companies that you are most interested in by reading their job postings and applying online.
For me, I started applying and interviewing for full-time jobs in the fall quarter of my senior year. I interviewed throughout the year with various organizations, some better than others. I ended up interviewing with what I thought was my dream job (until the interview and I had a chance to meet and learn about the organization) the week of graduation. I held off on companies that ended up pulling offers for that interview, but ended up at a very good company (that I co-oped with) a few weeks after graduation.