The Christkindelsmarkt in Nuremberg is quite famous, the also have the biggest Feuerzangenbowle in the world (at least they claim it).
The english translation of Feuerzangenbowle according to dict.leo.org would be: "mulled wine with a rum-soaked sugarloaf lit above it"
If you like a medieval touch, then you could visit the christmas market in Esslingen (near Stuttgart).