Like many other faculty members, I write letters of recommendation quite frequently. The context varies: sometimes for undergraduates applying to graduate or professional school or for jobs in the real world, sometimes for graduate students applying for academic or non-academic positions. Many students know instinctively how to handle this, but others find that asking for a reference feels awkward, and are not sure exactly what to do. Here is some all-purpose advice.
Most professors, and all of the ones I know, are very happy to write letters for students. It takes a little work, but nobody minds, because we genuinely want to see our students succeed as they move on in life and careers. There are a few things that you can do to make it easier for your recommenders. The first is to ask well in advance. There's no hard-and-fast rule, but I think that you should allow at least 2 weeks before a deadline, and several weeks if that's possible. The main reason for this is that it's actually hard to write a good reference letter, and it takes time (at least for me) to formulate things properly. Many graduate schools these days do their applications on-line, and often ask the recommenders to go through a series of forms in addition to sending a reference letters. This takes a little time, and it's better for all concerned if it's not done in a rush.
If you've already asked for recommendations for a number of schools and need to add a couple more, then timing is less of an issue if it's relatively short notice, since I'm probably going to use the same letter for all schools. Also, if you don't have all of your materials in hand (see below), then it still makes sense to ask early rather than be last-minute, so at least I can start thinking about what I'm going to say.
When it comes to grad schools and/or references for a job, it's always a good idea to supply an up-to-date CV and a list of places to which letters should be sent, along with addresses and deadlines. Usually, if you are applying to a graduate school, you will be writing a short essay (`statement of purpose' or some title like that) as part of the application. I find it useful in writing a reference to have a copy of this sort of essay. I may also offer you comments on content and/or writing, which of course you're free to ignore. If you are a graduate student, then you should give me a copy of your thesis/research summary and plans for future research, as well as your teaching statement.
Finally, it's perfectly reasonable to remind your references of approaching deadlines, and to politely inquire if the letter has been sent. With on-line applications, you typically get electronic notification when a recommendation has been submitted, so you can keep track that way.