Has your father done any DNA testing? He should do the yDNA test, at least 37 markers. He should also do the autosomal DNA test.
http://www.familytreedna.com has some very good educational information about these tests. The autosomal test will help you find cousins on both sides of his family. The y-test will help only on the paternal side of the family. Both can be very helpful for adoptees.