I would say that it is never too early to start looking, although right now it's going to be really tough to find anything. I was in Grand Cayman on January 19 and talked to several realtors...none of them had any rental properties. There is a lot of construction going on right now, so I'm hoping that there will be a lot more housing in the near future (as in the beginning of the may semester). I've heard that many places will be finished starting the beginning of march (keep your fingers crossed).
As far as where to live...I'd say you should try to live either in West Bay, 7 mile beach, or Georgetown. Anything further east is going to start to be pretty far from campus.
Just my two cents...anyone else feel free to reply.
Baker