Supposedly, there are two origins for this expression:
One supposed origin is that the phrase derives from mythology. Dogs and wolves were attendants to Odin, the god of storms, and sailors associated them with rain. Witches, who often took the form of their familiars - cats, are supposed to have ridden the wind. Well, some evidence would be nice. There doesn't appear to be any to support this notion.
It has also been suggested that cats and dogs were washed from roofs during heavy weather.
So it always made me wonder, if in Portuguese people thought of a similar way to describe a heavy rain. Specially if it involves cats and dogs...