So, the two descriptions here "céu escuro + nuvens pesadas" = céu encoberto, céu nublado.
Only that 'céu nublado" (cloudy day) sometimes doesn´t necessarily might have heavy clouds and grey skies, see? A cloudy day without being overcast (completamente coberto).
So, there´s some room to intersection on meaning and usage, that´s why I said that you won´t be sued if you use one or the other with the meaning of "nublado/encoberto".
But be aware that one of the definitions of overcast is "cloudy, darkened", which adds some nuance to it.http://www.thesaurus.com/browse/overcast