I have heard that it is a good practice or even necessary to ask for our potential referees' permission before we include their contact details in our CVs. Is it also a good practice to keep them informed about which positions we are applying for and the status of each of these applications? Is it good or necessary to update them how each of our application went, whether rejected or invited for an interview, or should we be selective?
Asking for permission before giving anyone's contact details in a CV as a potential reference should go without saying. Both for their sake and for yours. You want to be sure they can write you a good, relevant recommendation for the position(s) you are applying for, and presuming that someone has the time to write a recommendation letter without asking them is just rude.
I don't think it's possible to write really excellent recommendation letters without knowing where you are applying. At the very least, they would need to know whether the schools you are applying to are liberal arts schools or R1 schools, to know how to focus the letter. If they are familiar with a department or someone working in a department where you are applying, the letter could (if they have the time / inclination) be tailored even more.
I've always been told that it's good etiquette to inform anyone who wrote you a recommendation letter for anything what happened to the application. A quick email or note (or even stopping by their office) to say thank you again and tell them where you will be going next year, even if it's not to the place they wrote the recommendation letter for is the polite thing to do.