I always use the Left Luggage facilities (there are three, two of them in T1 and one in T2). I've always found them easy to use for short-term storage.
However, another alternative is to use the lockers in the Hauptbahnhof. The attached map shows the location of the lockers (Schließfach):
http://www.bahnhof.de/site/shared/de...furt__main.pdf