3 - 4 years since I graduated, how should I time asking for recommendations?
My recommendation is similar to those posted in comments. I worked for several years before applying to graduate school and did not stay in touch with my professors during that time. Approximately 4 months before I applied to graduate school, I sent each professor a brief (1 paragraph) email explaining my graduate education plans and career interests, and asking if they would be willing to write letters of recommendation, which would be due in November. I also indicated that if they were willing, I would send them my CV and a summary sheet of my college activities for their reference. I contacted them via email, as I lived in a different state than the college, and face-to-face meetings were impractical.

When they agreed to write the letters I sent them:


A summary sheet listing each program I was applying to. For each program I listed the address and contact person (so the letter could be properly addressed), 1 line about why the program interested me, the names of faculty I was interested in, the application deadline, and specific application letter forms or links to online applications, if relevant. 
My CV
A summary sheet highlighting specific grades in major-related courses; research projects and activities I engaged in during college; a 1 paragraph narrative explaining what I had done since graduating and why I was interested in pursuing another degree; and a list of courses I took with that particular professor/letter writer, along with the grade for the course and any special projects completed in those courses. Try to keep this to 1 page.


Although this sounds like a lot of information, work to keep it as brief as possible, while ensuring the professor has the information they need to write a strong letter.

You may choose to time this differently, but the four month window ensured that I had committed to applying and gave me time to identify alternative writers if they had declined. I'm not sure it would be useful to ask your professors a year in advance, as 1) your plans may change, and 2) they may not recall a commitment they make that far in advance. That said, I would make initial contact in the summer before you apply; if you wait until the school year kicks into full gear, your email might get lost in the shuffle. When I was applying I was advised by multiple people to provide all materials to my letter-writers a minimum of 2 months prior to the deadline. Many schools require letters to be written on specific forms, have surveys your letter writers are asked to complete, or even ask the letters be submitted online; it's unlikely the most recent application will be available more than a few months prior to the application deadline.

A few final notes: 


Be sure to ask if they feel they can write you a strong letter, not just a letter of recommendation. Most faculty will be honest about this. 
Send your letter writers an email two weeks prior to the application deadline to thank them and remind them of the approaching deadline. Many online applications will indicate when your letters of recommendation have been uploaded. 
Be sure to thank them, both when they agree to write the letter and when the letter is submitted. Consider writing and mailing a formal thank you note, once the application is submitted. Also, contact them once you're accepted and have decided on a school; they like to know how it's worked out!