A good starting point is the Association for Computer Genealogy (CompGen): there you will find not only digitized sources but also an extensive wiki on genealogy with many, many links and information about archives, etc., at GenWiki.
In Germany, family research usually begins with church records. Many of these are now available online in digital form (Protestant records at Archion, Catholic records at Matricula), although some are not yet available.
When it comes to former German territories such as East Prussia or Silesia, specialized genealogical associations are often a good starting point, as they have detailed knowledge of where specific archival materials can be found. For example, the Association for Family Research in East and West Prussia and others.
I can also highly recommend the CompGen Discourse forum: there are individual categories for specific regions. Link
It is important to know which religion your grandparents belonged to. As David has already mentioned, the Evangelical records are available for a fee through Archion.
Another source is FamilySearch.
You can register there for free and search the catalog by the town your grandparents came from. If you’re lucky, you’ll find your grandparents’ town there and can directly view the church books.
With a bit of luck, someone has already created a local family book. East Prussia was fiercely contested during World War II, and many church books were destroyed.
Ancestry and MyHeritage could also be helpful. They might lead you to a new lead. However, you should approach the data there with caution, as many family trees are hastily constructed. But they are sufficient for finding a lead.
A DNA test via MyHeritage (which has more European testers) could also help you find a direction.
If you’d like, I can assist you a bit with your research. Feel free to send me your grandparents’ data via private message.