I'm just about to contact a potential supervisor, but am not sure what to write. I'll tell him why I'm interested in his research, include a CV and ask him about financing possibilities. Should I say something else? Should I include names of academic referees, or can that wait until a formal application? They haven't advertised a position, but I wanted to ask anyway, because their research is really interesting.

Well try to include your referance's email address as a part of your CV in case they want to email. Also tell your referee's that they might email. No need for them to advertise they might still respond if your background is good

You're doing the right thing. Your referees should be included on your CV.

I wrote those letters to several professors. I wrote about my interest in his past works, my education and research experience (where and what), my future research interests, and asked him whether he might be interested in supervising me as a PhD student. I got good responses mostly. Alghouth some of them answered only in two or three weeks. And not all of them were interested in taking new PhD students!