Church records from Austria, the Czech Republic, and some areas in Poland and Hungary are online at various archives in Europe, and freely available. There are no comprehensive indices, but some of the church books are individually indexed. Some (generally fewer) records are available at FamilySearch. However, it is essential to know what town or village they are from. Knowing their religion is useful, but not absolutely essential.
Many people from various locations in the Empire went to Vienna, as it was the capital. Some of the population indexes there can be helpful. Joining Genteam, for Austrian research, can be helpful as there are a number of useful indices there. Genteam is free.