The Jews were targeted not because of their religion but on basis of racial characteristics.
According to the science of the day, eugenics, this could be easily detected based on parentage and physical characteristics.
Thus marriage and birth certificates were a major source of information, and where that wasn't conclusive (say immigrants), actual measurements of things like the slope of the forehead and the dimensions and shape of the nose were used (and in many cases pure speculation, just like in the past just accusing someone of being a witch made them a witch, nowadays the same process is responsible for putting many a person behind bars for being a pedophile who never touched a child).
The main reason for the persecution was economic, combined with historical prejudice (that was and still is deeply rooted throughout Europe). The German economy was in tatters, but the Jews were as a group doing a lot better than the population at large. When the government needed a scape goat, they were a logical group to target.
Mind this wasn't at all limited to Germany, the same went on in many countries, foremost of all the USSR.
Historically of course the Jews were strangers, with weird customs, rather insular, with a different religion, in countries that were very much homogenous in their cultural and religious makeup (and to a large degree in many countries largely racially homogenous as well). That set them apart, people were suspicious of them, and the Nazi propaganda built on that to blame them for the economic woes of the late 1920s and 1930s (the fact that many banks were owned by them, and Jewish owned businesses doing overall better than German owned businesses made that easier).
To a large degree the same goes on to this day, see how "evil bankers" are blamed on the economic crisis that started in 2007 even though they had very little to do with it (most were hit as hard as or harder than anyone else). They're just easy and obvious targets.