From a top down perspective: Various prewar governments routinely asked people their religion during the standard census.

IBMs European subsidiary Dehomag was in charge of collating the census in most countries using leased American kit. So in each country the Nazi's invaded they could just do an updated census using common Hollerith IT hardware and cross reference it with previous censuses and police records.

To find the Jews they just ran a punchcard collation on the census data to sort by religion. The resulting Jewish punch cards would be mail merged into letters asking Jews by name to turn up at the relevant railway station at a certain time. Think a steam punk Facebook targeted ad.

This was the same technique and hardware, that IBM America used to get American Japanese into American camps. Only America collated by race rather than religion.

The census hardware was the same across most countries, but the staffs enthusiasm varied by conquered countries. Belgium was enthusiastic and tagged most of their Jews. France wasn't enthusiastic, their head Hollerith man died in a concentration camp after not helping.

Since German law protected the lives of German citizens, the trains typically would take German Jews to camps outside the borders of Germany. Once in the camp their details were entered into another Hollerith punch cardcomputer, noting religion, age, gender, work skills, health, sexual orientation etc. Then when they needed more workers or less heads they run a collation to build a list. Staff would read out the list to get people into the relevant work party. Then send the work party off to work or die.

The book IBM and the Holocaust by Edwin Black goes into detail.

But short version was everyone needed to carry ID that specified their religion. The information was centrally stored. And the Nazis just searched on the Religion field in their punch-card census database that expanded with each country they invaded.

Ironically the Census data also tracked Nazi party affiliation. So when the Allies conquered Germany, American IBM staff claimed "their" Hollerith machines from the Concentration camps, loaded them with the German census data and generated lists of Nazi's.