Just got back from Berlin & had a great time from the tips found on this thread!
Thought I'd add some of my own though...
If you head over to the West (which I would recommend for contrast alone) in Charlottenburg there's one street: Suarezstrasse, which is full of antique shops & is having a festival or something at the beginning of September (I think) where they close the street & have like an antique fair.
The best shop was Tony Durante's. Not only was his stock meticulously vetted & perfect (every piece I wanted to take home) but he was absolutely lovely too. He told us stories about every piece, gave me tips on starting my own shop, told us about serving Kate Moss in his London store & showed us garments he never even put out to sell because they were so special too him. It is more pricey than most vintage shops in Berlin, but they're completely justified because they are properly quality pieces.
Also I would say that if you go to Mauerpark market, to go to Arkonaplatz market first, it's much smaller but most of the stock is better quality (I got a 40s silk dress for €30) & it's less touristy too.
Also, whilst I would recommend Garage, I would stay away from Made In Berlin & Colours, they're by the same people, but they're overpriced, bad quality & practically on every corner. I prefer to work a bit harder for my clothes, but I was really unimpressed! Plus the Bauhaus Archiv is really near Garage, which was properly amazing.