Sachverhalt: A. Die aus Thailand stammende Y._ (geb. 1961) war in erster Ehe mit dem thailändischen Staatsangehörigen A._ verheiratet. Dieser Verbindung entsprossen zwei Knaben, nämlich Z._ (geb. 1981) und X._ (geb. 26. Dezember 1985). 1989 wurde diese Ehe geschieden. Im Jahre 1991 reiste Y._ in die Schweiz, wo sie den Schweizer B._ heiratete und in der Folge das Schweizer Bürgerrecht erhielt. Die beiden Kinder Z._ und X._ blieben in Thailand. Am 12. November 1998 wurde die Ehe von B._ und Y._ geschieden. Am 22. März 2002 reiste der jüngere Sohn von Y._, X._, mit einem für drei Monate gültigen Besuchervisum in die Schweiz zu seiner Mutter. Am 30. Mai 2002 stellte Y._ ein Gesuch um Erteilung der Niederlassungsbewilligung für ihren Sohn zum Verbleib bei ihr. Mit Verfügung vom 30. September 2002 wies das Migrationsamt des Kantons Zürich nach Einholung ergänzender Angaben das Gesuch ab. Zur Begründung wurde im Wesentlichen ausgeführt, der Sohn habe keine vorrangige Beziehung zur Mutter. Den dagegen erhobenen Rekurs wies der Regierungsrat des Kantons Zürich am 9. Juli 2003 ab. Das Verwaltungsgericht des Kantons Zürich bestätigte diesen Entscheid am 14. Januar 2004 auf Beschwerde hin. B. Mit gemeinsamer Eingabe vom 17. März 2004 führen X._ und Y._ Verwaltungsgerichtsbeschwerde beim Bundesgericht und beantragen, den Entscheid des Verwaltungsgerichts vom 14. Januar 2004 aufzuheben; ferner sei "die Sache zur Vervollständigung der Sachverhaltsfeststellung an die Vorinstanz zurückzuweisen; diese sei anzuweisen, den Beschwerdeführer persönlich anzuhören und Frau C._ als Zeugin zu befragen". Gleichzeitig verlangen sie für das Verfahren vor Bundesgericht die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. Die Staatskanzlei des Kantons Zürich (für den Regierungsrat) und das Bundesamt für Zuwanderung, Integration und Auswanderung schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich beantragt, die Verwaltungsgerichtsbeschwerde abzuweisen, soweit darauf einzutreten sei. C. Am 16. April 2004 erkannte der Abteilungspräsident der Beschwerde - antragsgemäss - aufschiebende Wirkung zu. 