First off, none of the cities you mention are in Baden Wuerttemburg, they are in Bavaria (Bayern). And yes it is likely to be quite cold even if it does not snow the 3-4 days you are there. I've been in Nuremberg in October and Munich in both October and April and it was cold at both times. There was even snow in Munich as late as April.
Fussen is up in the mountains and yes it is a nice place, but more for a day trip from Munich rather than a place to stay for very long. The castles are great, but somewhat touristy.
For weather trends check Wunderground.com. The source link is for the month of December 2005 in Munich. It shows no snow, but cold and windy on average.
So you will want a heavy jacket that will block the wind, and perhaps a sweater to layer underneath. A pair of jeans will probably cut the cold decently; but if you are truly sensitive to it think about long underwear or flannel to wear underneath. As for shoes, pick something like a boot rather than a tennis shoe. Tall socks will help prevent wind up the pants legs as well. Even if it does snow, most cities will have it cleared off enough that you won't be walking ankle deep. One thing to mention about layering, if it is cold outside a lot of the buildings will be heated so whatever you wear make sure you can take off whatever you need to be comfortable. Pack (or acquire) an umbrella.
All this said, Germany CAN be unpredictable weather-wise. I saw some nice short-sleeve days in Freiburg (other side of the black forest from Munich) in January. So if you are only going to be there a few days don't drop a lot of money on clothes you won't wear in Malaysia; but a heavy jacket will most likely be your best bet. You can always buy extra layers in Germany.
As a last travel hint, look for the Christmas Markets in the towns you will be in. They are only up for the Christmas season; but are real cultural experiences and often vary from town to town having local traditions and specialities.