I went to a major coastal city and I started looking heavily in September of CA3 year. In mid October I interviewed at five locations and then I signed a contract by mid November.
Two of my residency peers had contracts at the end of their CA2 year because they were going back to their hometown which were smaller cities.
Upper midwest, the world is your oyster. People gravitate towards the bigger cities/coastal areas (myself included). I'd say it's never really too early to start your due diligence when contacting groups. Anytime CA2 year is a good head start on things. Get a nice CV together and research hospitals online. Make some phone calls and find out who the group president is and get his/her phone number or email address. You can generally get a lot of information on the hospital website and then doing a physician search for anesthesiology, most have a phone number that will get you some where. Then introduce yourself, state where you are in your training and that you're interested in the area. They'll usually have you send a CV in.
Right now you should make a short list of states you're interested in and research licensing requirements. They can vary widely. If they're a state that requires FCVS then start working on it now, it's very very slow and painful. Plan on 6 or more months for a license and credentialling at a hospital. If you work backwards you can do the math, you need to have a job contract signed by Jan/Feb your CA3 year to start in July. Some states are much easier to get a license (Indiana I've heard is 2 weeks, $200), but you should get some idea of what ones are a big hassle. The short list is Florida, Texas, California, Mass.