Start looking for a doula well before your due date. Most only take a few clients a month, so you need to book early. Ask your doctor, midwife, childbirth educator, friends and anyone else you trust for recommendations. Consider what you want.
Some doulas have nursing degrees.
Others are trained in massage or acupuncture. Several organizations certify doulas, but it's a new process, so most won't have certification. Interview at least two. Find out exactly what services are provided and how much they cost. Choose someone whose ideas about birth are similar to yours.