I battled with how to approach this when I first set out on my DNA testing 'saga' about two years ago and have learned a few things over now 60 plus completed kits that I manage across multiple family lines over the last 2 years.
1) Form letters = Failure; I cannot emphasize this enough. Just like I don't like getting them, people are irritated by them and blow them off as SPAM. Much like those mass mailings you get from GEDMATCH.com matches who just used an automated mailer to all of their matches with nothing about themselves... the following points go to not making helping you make it not a form letter.
2) Share something about yourself, break down that barrier by exposing and sharing. It sets a good precedent that you are just not looking to 'take'.
3) Personalize correspondence; learn something about them and let them know how you found them. Some people get defensive if you think you have been researching or stalking them and so be open.
4) Be crystal clear on your intent, project goals, and how you will treat the information and offer to give them full access to the test results once the results are complete.
5) Share information about the research you have done so far; especially how you think you are related.
6) Inform them and let them know exactly what tests you intend to perform and how it will be used. I am straight forward with what I am wanting from them usually in initial contact and ALWAYS pair it with what I am offering in terms of information and collaboration. Information and collaboration as noted above I have found to be one of my strongest motivators for people.
7) Enable them to do the test themselves by inform them how they to can do the tests themselves and what service you will be using (IMPORTANT: Keep this consistent) This both allows them to checkout the service you will be using as well as do it themselves which I have had several now do. It takes them longer usually but they do usually it. Do not forget to ask if they have already tested.
8) Diverse Communication: Use multiple forms of communication to establish contact, sometimes you need to resort to cold calling from the white pages them or in at least one 'stopping by' (see next bullet). I know multiple people I am in contact do not do email or Facebook and require a phone call. I also used to loath Facebook but found it to be great tool for genealogical research / stalking of tracking people down and collecting basic information. Sometimes it is not them that you can get in contact with.. but their children, uncle, or acquaintance that is posting about genealogy on Facebook that could break the ice with them.
9) Get the test into their hands; I like using FamilyTreeDNA and pre-purchasing 5-10 kits ahead of time for $12 bucks a pop and then carrying them with me when I travel or including them with letters to those that do not respond to electronic communication. Then if they send them in you then pay for the test vs. pre-purchasing tests that never get sent in.
10) Collaboration: Stay in communication and follow-up with them; if you fail to do this regularly they may not send in the test, talk to someone else who needs to assist, or provide critical information to help fill in the paperwork trail. This also builds collaboration.. a private Facebook group is an easy way to keep in contact with multiple individuals.
11) Be Accepting of No and do not be pushy. There are a lot of different reasons people say 'No' and you need to be accepting of it and do not be pushy. Some of my contacts I had to follow-up every couple of months (not usually weeks) and remind them.. one took about a year and a half and when they did finally send in their kit it was worth its weight in gold.
The common ones I run into are A) I have not interest in genealogy and do not care. This one I can usually over time tactfully talk them out of by saying others care and you would be helping them. B) Privacy; this likely includes simple privacy and possibly concerns about linking to crimes or children they may or may not be aware exist. C) They simply do not want to know, they may have suspected there family line is not as what it has been described and they are content not know and do not want to 'rock the boat'.
11) Bonus: Offer an autosomal DNA test to their spouse or split the cost with them as an incentive to assist in their own genealogical research.
12) Bonus: Focus on getting matches you find on different sites to transfer to a central site or sites. I push for FamilyTreeDNA and GEDMatch and offer to pay the transfer fee.
Cautionary Advise:
I would advise in every way though against telling them how much it will cost you or talk about it unless they ask. This will put people off; especially for those with a conscience that can't 'process' someone willing to spend that amount of money on them.
I have heard, but not personally experienced, is I have heard of people requesting additional financial compensation for performing the test (You are already forking up a couple hundred dollars right, so what is a bit more). I have not paid someone to take a test to date, and I would strongly caution against this and only even consider it if you are very confident it is your only option. Then only agree to pay once they have delivered the results to the lab; if not when the results are posted showing they just didn't have some random person take it in there stead.
The strategy above statistically over time has worked VERY well for me. Of the 60 some kits I manage some they did the tests with me having to ask, but of those I have asked I currently only have 2 'no' responses and 4 'difficult' to establish contact or get an answer out of one way or another but of those 2 I have established contact with their family member so I consider 'in-process'; so I believe this is about an 80-90% success rate.
All-in-all it is very much a test of patience and expensive proposition but I have learned so much from DNA testing when combined with other information it has been personally worth it to myself.