Sachverhalt: A. Der 1947 geborene, geschiedene Z._ verstarb am 29. Januar 2000. Mit Erklärung vom 22. September 1999 hatte er bei der Winterthur-Columna, Stiftung für die Zusatzvorsorge (nachfolgend: Winterthur-Columna), beantragt, dass für den Fall seines Todes vor Erreichen des Pensionsalters seine Brüder X._ und Y._ und seine Lebenspartnerin A._ in seiner Vorsorgeversicherung (Vertrag Nr. ........) zu je einem Drittel zu begünstigen seien. Eine Anfrage von X._ vom 25. Januar 2001 beantwortete die Winterthur-Columna am 29. Februar 2001 dahingehend, dass das Todesfallkapital (von Fr. 890'903.-) den Kindern des Verstorbenen ausbezahlt worden sei, weil gemäss reglementarischer Begünstigungsordnung die Nachkommen vor den Geschwistern aufgeführt seien. B. X._ und Y._ erhoben am 28. Mai 2001 beim Zivilgericht Basel-Stadt Klage mit dem Rechtsbegehren, die Winterthur-Columna sei zu verpflichten, ihnen den Betrag von Fr. 593'935.- nebst Zins von 6 % seit 1. März 2000 zu bezahlen. Das angerufene Gericht trat auf die Klage mangels Zuständigkeit nicht ein (Entscheid vom 4. März 2002) und überwies die Akten dem Kantonsgericht Basel-Landschaft, Abteilung Sozialversicherungsrecht, welches die Klage mit Entscheid vom 26. Juni 2002 abwies. C. Mit Verwaltungsgerichtsbeschwerde erneuern X._ und Y._ das im kantonalen Verfahren gestellte Rechtsbegehren. Während die Winterthur-Columna auf Abweisung der Verwaltungsgerichtsbeschwerde schliesst, verzichtet das Bundesamt für Sozialversicherung (BSV) auf eine Vernehmlassung. 