From Cologne,
Aachen is easy to reach. The market there is quite nice (try Aachener Printen, a special type of spicy chocolate biscuits), and don't miss the cathedral, Charlemagne's church, built around 800 A. D.
Both for Christmas markets and for the city, I definitely recommend
Dresden. One of the oldest and most famous Christmas markets in Germany. Here you'll find the real traditional woodcarvings from the Erzgebirge. Dresden is worth staying for a couple of days.
The one at Leipzig is said to be nice, too, but I haven't visited it myself.
You don't mention the exact dates of your trip - I guess you know that practically all German Christmas markets terminate on Dec 23 or Dec 24 around noon, so coming here for the Christmas holidays would be a disappointment.
Advent, i. e. the four weeks before Christmas, are much better to soak up some Christmas feeling. Streets and shops are decorated, and any city or town has its Christmas market.