Sachverhalt:
A. Die PKG Pensionskasse (im Folgenden: PKG), zahlte als Rechtsnachfolgerin der Providentia, Schweizerische Lebensversicherungs-Gesellschaft, bei welcher der im August 2004 verstorbene Z._ berufsvorsorgeversichert gewesen war, das Todesfallkapital des Z._ an B._ aus, die mit dem Verstorbenen seit dem Jahre 1989 im Konkubinat gelebt hatte. Die PKG berief sich dabei auf Art. 7.5 lit. c ihres Vorsorgereglements (in der Fassung vom 1. Januar 2002), wonach das Todesfallkapital dem Lebenspartner ausbezahlt wird, "mit dem die versicherte Person unter gegenseitig vereinbarter Unterstützungspflicht nachweislich in den letzten fünf Jahren bis zu ihrem Tode ununterbrochen eine Lebensgemeinschaft geführt hat". Eine in der Folge von den Söhnen des Z._, M._ und R._, erhobene Klage gegen die PKG hiess das Verwaltungsgericht des Kantons Luzern nach Beiladung der B._ zum Verfahren am 28. Februar 2008 gut und verpflichtete die PKG, das Todesfallkapital an M._ und R._ auszuzahlen. Nachdem sowohl B._ als auch die PKG je Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben hatten, vereinigte das Bundesgericht die Verfahren und hiess die Beschwerden mit Urteil 9C_267/2008 und 9C_318/2008 vom 10. Dezember 2008 in dem Sinne gut, als es den angefochtenen Entscheid aufhob und die Sache an die Vorinstanz zurückwies, damit sie weitere Abklärungen tätige zur Klärung der Frage, ob zwischen Z._ und B._ eine Bereitschaft zur gegenseitigen Unterstützung im Bedarfsfall bestanden habe, sich hiezu sachverhaltlich äussere und über die Begünstigung der B._ erneut entscheide.
B. Das Verwaltungsgericht zog die Steuerakten betreffend Z._ und B._ der Jahre 1999-2004 bei, gab den Parteien Gelegenheit zur Stellungnahme und wies die Klage des M._ und des R._ mit Entscheid vom 15. Juni 2009 ab.
C. M._ und R._ führen Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragen die Aufhebung des angefochtenen Entscheides und die Gutheissung ihrer Klage, eventualiter die Rückweisung der Sache zur Neubeurteilung an die Vorinstanz.

Erwägungen:
1. Streitig und zu prüfen ist, ob die - antizipierte - vorinstanzliche Beweiswürdigung Bundesrecht verletzt.
1.1 Die konkrete Beweiswürdigung ist Tatfrage. Sie ist somit für das Bundesgericht nur dann nicht verbindlich, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann. Als Rechtsfrage frei überprüfbar sind hingegen Verletzungen des Grundsatzes der freien Beweiswürdigung (<ref-ruling> E. 3a S. 352) sowie des Untersuchungsgrundsatzes (<ref-law>).
1.2 Im Sozialversicherungsrecht hat der Richter seinen Entscheid, sofern das Gesetz nicht etwas Abweichendes vorsieht, nach dem Beweisgrad der überwiegenden Wahrscheinlichkeit zu fällen. Die blosse Möglichkeit eines bestimmten Sachverhalts genügt den Beweisanforderungen nicht. Der Richter hat vielmehr jener Sachverhaltsdarstellung zu folgen, die er von allen möglichen Geschehensabläufen als die wahrscheinlichste würdigt (<ref-ruling> E. 2.1 S. 153 mit Hinweisen).
1.3 Der Beweis dafür, dass sich Konkubinatspartner die Treue halten und sich Beistand leisten wie Eheleute, ist schwierig zu erbringen. Aus diesem Grund hat das Bundesgericht eine Tatsachenvermutung in dem Sinne aufgestellt, dass bei einem Konkubinat, welches fünf Jahre gedauert hat, grundsätzlich davon auszugehen ist, es handle sich um eine Schicksalsgemeinschaft ähnlich einer Ehe. Diejenige Prozesspartei, welche Rechte aus einem Konkubinat ableiten will, hat somit nur die Vermutungsbasis zu beweisen, d.h. zu beweisen, dass ein Konkubinat vorliegt und dass dieses (mindestens) fünf Jahre gedauert hat. Gelingt ihr dies, greift die erwähnte Vermutungsfolge. Es ist alsdann Sache der Gegenpartei zu beweisen, das Konkubinat sei nicht so eng und stabil gewesen, dass die Konkubinatspartner voneinander Beistand und Unterstützung ähnlich wie in einer Ehe erwarten konnten (<ref-ruling> E. 2 S. 190 f.; <ref-ruling> E. 1b S. 298; vgl. Urteil 5C.70/2003 vom 2. Juni 2003 in: FamPra.ch 2003 S. 905).
2. 2.1 Das kantonale Gericht erwog in Würdigung der beigezogenen Steuerakten, sowohl der verstorbene Z._ als auch B._ seien wirtschaftlich unabhängig gewesen und hätten für ihren Lebensunterhalt selbst aufkommen können. Ob eine gegenseitig vereinbarte Unterstützungspflicht bestanden habe, könne nur hypothetisch entschieden werden, wobei aufgrund der unbestrittenen Konkubinatsdauer von rund 15 Jahren die Bereitschaft zur gegenseitigen Unterstützung im Bedarfsfall ohne weiteres unterstellt werden könne. Alles andere müsse als "lebensfremd" bezeichnet werden. Auf weitere Beweismassnahmen sei, auch angesichts der unterschriftlich bestätigten Angaben von B._, wonach eine eheähnliche Gemeinschaft gelebt worden sei und die Konkubinatspartner für den Unterhalt der gemeinsam bewohnten Liegenschaft zusammen aufgekommen seien, in antizipierter Beweiswürdigung zu verzichten.
2.2 Die Beschwerdeführer rügen, eine gegenseitige Unterstützungspflicht ergebe sich nicht aus den Umständen. Die von der Vorinstanz unterstellte Hypothese reiche nicht aus, um einen Sachverhalt als bewiesen anzusehen, zumal aus den edierten Steuerunterlagen hervorgehe, dass Z._ und B._ wirtschaftlich voneinander unabhängig gewesen seien. Auch ein länger als fünf Jahre bestandenes Konkubinat genüge nicht als Nachweis einer gegenseitig vereinbarten Unterstützungspflicht im Bedarfsfall; für eine solche müsse vielmehr der volle Beweis erbracht werden, was der Beschwerdegegnerin und der im vorinstanzlichen Verfahren beigeladenen B._ nicht gelungen sei. Der angefochtene Entscheid verletze insofern Bundesrecht (<ref-law>, Art. 73 Abs. 2 BVG sowie <ref-law> und <ref-law>). Dies gelte umso mehr, als die damaligen Konkubinatspartner beispielsweise gemeinsame Konten eingerichtet hätten, wenn sie für ihre Lebenshaltungskosten gemeinsam hätten aufkommen wollen, was nachweislich nicht zugetroffen habe.
3. Es ist unbestritten, dass B._ und der verstorbene Z._ seit dem Jahre 1989 und bis zum Tode des Z._ im August 2004 zusammen gelebt hatten. Es ist nicht willkürlich, wenn die Vorinstanz daraus gefolgert hat, es liege ein Konkubinat vor. Damit kommt die Tatsachenvermutung zum Tragen, wonach sie sich Beistand leisteten wie Eheleute (E. 1.3 hievor). Die Beschwerdeführer bringen keine Gründe vor und zeigen keine Sachumstände auf, die es als überzeugend (nachvollziehbar) erscheinen lassen, dass Z._ und B._ trotz der langen Dauer ihres Konkubinates keine Absicht - im Sinne einer konkludenten Vereinbarung - gehegt hatten, sich im Bedarfsfall gegenseitig zu unterstützen, oder die an dieser Tatsachenvermutung erhebliche Zweifel erwecken. Die blosse Behauptung in der Beschwerde, die sich aus den beigezogenen Steuerakten ergebende, theoretisch möglich gewesene wirtschaftliche Unabhängigkeit sei von den Parteien auch gelebt worden, was das Fehlen gemeinsamer Bankkonti zeige, und den daraus gezogenen Schluss der Beschwerdeführer, es habe den Konkubinatspartnern an der Bereitschaft zur gegenseitigen Unterstützung gefehlt, hat die Vorinstanz in bundesrechtskonformer Beweiswürdigung nicht als erbrachten Gegenbeweis anerkannt. Auch soweit das kantonale Gericht den Umstand, dass B._ sowohl ein höheres Einkommen als auch ein grösseres Vermögen versteuerte als Z._, nicht als Indiz für eine fehlende gegenseitige Unterstützungsbereitschaft würdigte, ist dies nicht zu beanstanden.
Schliesslich ist es weder unhaltbar noch verstösst es gegen den Untersuchungsgrundsatz (Art. 73 Abs. 2 BVG), dass das kantonale Gericht die unterschriftlich bestätigten Ausführungen der B._, wonach sie und Z._ sich im Rahmen der von ihnen langjährig gelebten eheähnlichen Gemeinschaft sowohl den Unterhalt der gemeinsam bewohnten Liegenschaft als auch die Haushaltskosten und Neuanschaffungen geteilt hätten, ohne eine schriftliche Vereinbarung getroffen oder entsprechende Quittungen ausgestellt zu haben, in ihrer Beweiswürdigung berücksichtigt und über den Beizug der Steuerakten hinaus auf beweisrechtliche Weiterungen verzichtet hat.
4. Die Gerichtskosten werden den Beschwerdeführern als unterliegender Partei auferlegt (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 500.- werden den Beschwerdeführern auferlegt.
3. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Luzern, Sozialversicherungsrechtliche Abteilung, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 23. Oktober 2009
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Bollinger Hammerle