There are so many individual variables to consider here that nobody can truly tell you when you should begin looking for housing. I am matriculating this year and already have a deposit down on an apartment that I'm willing to forego if a waitlist offer from my top choice comes through. Otherwise, I like the peace of mind of knowing that I have a place ready that will allow me to get settled in a solid month before orientation. My class Facebook page also has a lot of housing information being passed around, including a roommate sign up sheet and multiple opportunities to take over a room in an existing lease due to graduating students.
My general advice is the sooner the better, even to just get an idea of what housing will cost and you can begin making decisions on what you are seeking. Bear in mind that many leases require 60 days notice from evacuating tenants, and they may not have availability information yet for someone who wants to move in June or beyond.
So it all comes down to when you want to move, finding a location that's adequate for your needs, whether you want to find a roommate among your peers or live alone, what you want to spend, etc.