I see that this question has been asked and answered with a plethora of information as well as the notation that a lot of archives were destroyed in 1945. However, I thought it might be worth asking again. The catch-22 being that I have no information on my grandfather's service in the German army and the only way to search is by soldiers' unit information-which I do not have. All I know is that he was born near Graz, Austria served in the German Army and was born in November 1896. Is there another way to search for records of soldiers without having their unit information?
The answer provided on Finding information on German soldiers from World War I and World War II? is helpful here too, as you don't necessarily need a unit for your research.
If he was injured, went missing or became a POW, you will find him in the Verlustlisten (by name). If he truly served in the German army (where do you know this from?) while originating from Austria, a service in the Bavarian Army is somewhat likely. The Bavarian records are availabe on Ancestry and can be searched by name.
For more details please see the first link. If you have photos in uniform or a name for us it might help too in making research proposals.
Given that Austro-Hungarian and German units coordinated on both the Eastern and later Italian Fronts you need to be sure that he actually served in the German Army. The Bavarians, while under overall command of the German High Command, maintained a "separate army as mentioned above and those records are searchable through Ancestors -- photocopies of the actual documents So be prepared to read 100 year old script!