Hi Talacharn,
I know your task is daunting, but my family is searching for the identity of our grandfather becuase our father was born out of wedlock in 1938. We had him take both the autosomal and YDNA tests. We used Ancestry and also uploaded the autosomal results up to MyHeritage for greater exposure for matching purposes.
If you choose to test using YDNA, may I suggest the YDNA111 for the best results? My father's results at the Y111 led to the last name of his potential father. Lower test levels just left us with a variety of different last names, which didn't really help us and were a waste of money. There's not much you can do with thousands of exact to close matches! The YDNA111 will be worth it!
The autosomal results gave us a number of potential 2nd-3rd cousins (Ancestry also identifies whether the matches are from the paternal side or the maternal side of the family).
We took a look at the closest match on the paternal side and looked at their tree. First thing we looked for in the tree was a MALE with the potential last name resulting from my father's YDNA111 results. If there's no tree, which isn't unusual, you can try to create a tree backwards with the closest match and see if you find someone with the WILLIAMS last name.
Lastly, there are free charts available to help you calculate potential relationships of your match's based on their cM results. Try familytreemagazine.com for help - type in How to Determine Relationships with Shared DNA Matches.
I hope this helps.
Jenn