Is there a difference between these two words or are they synonyms? I understand that both words describe weather conditions, that are colder, than just "холод". It does seem to me that "стужа" sounds harsher than "мороз", but I cannot explain it.
These two can be treated as synonyms, but there's a subtle difference.
First of all, I would say (and Vladimir Dal's dictionary would agree with me) that "стужа" (derived from "студа") is harsher than "мороз".
Secondly, by using "стужа" you can refer to a situation that is "colder than it should be", for example "стужа в доме" doesn't mean that it's -50 degrees celsius in the house, but rather that it's much colder than it should be. In a similar way you use the verb "остудить" (to cool down, e.g. a cup of tea which is supposed to be served hot) instead of "заморозить" (to freeze so that it turns into ice).
Finally, "стужа" is somewhat outdated. You would often find it in literature, but not so often in common speech today.
See http://slovardalja.net/word.php?wordid=39357 for "стужа".
See http://slovardalja.net/word.php?wordid=16004 for "мороз".
Oh, and both words can also refer to things other than atmospheric conditions.
You're right, "стужа" (or old-fashioned "студа") means "сильный мороз". You can consult Explanatory Dictionary of the Live Great Russian language by Vladimir Dal to get a comprehensive explanation of the words' meaning.
«Мороз» means only low temperature. At my point «мороз» often been used to indicate dry cold. And usually it's objective definition.
«Стужа» means not only low temperature but also a cold wind and/or humid cold. Usually it's subjective definition.
So, if «на улице мороз» — you can feel yourself comfort, but if «на улице стужа» — this means that you can't feel comfortably because of wind or humid.
Стужа is a dead of winter, мороз is a frost, which may happen every winter day.
Some synonyms are дубак - colloquail form of the frost, heard in all Siberia, and зусман. The later one comes via Yiddish from Odessa and also means frost, as I heard it from Hebrews. Also, Zusman is a widely known Yiddish family.