Sachverhalt:
A.a Der Schweizerische Baumeisterverband (SBV), die GBI Gewerkschaft Bau & Industrie (heute: Unia) sowie die Gewerkschaft SYNA schlossen am 12. November 2002 einen Gesamtarbeitsvertrag für den flexiblen Altersrücktritt im Bauhauptgewerbe (GAV FAR), mit dessen Vollzug die Stiftung für den flexiblen Altersrücktritt im Bauhauptgewerbe (Stiftung FAR) betraut ist. Durch Beschluss des Bundesrates vom 5. Juni 2003 wurde der GAV FAR teilweise allgemeinverbindlich erklärt.
A.b Im Oktober 2008 reichte der 1949 geborene Z._ bei der Stiftung FAR ein Gesuch um Ausrichtung einer Überbrückungsrente ab dem 1. Mai 2009 ein. Mit Schreiben vom 6. Februar 2009 verneinte die Stiftung FAR den Anspruch mit der Begründung, bei der Firma X._, bei der Z._ von November 1995 bis Februar 2004 beschäftigt war, habe es sich um einen Betonbohr- und Betonfräsebetrieb gehandelt, der nicht Mitglied des SBV gewesen und von der Allgemeinverbindlichkeit des GAV FAR durch den Bundesrat ausgenommen worden sei. Somit habe Z._ die Anspruchsvoraussetzungen für eine Überbrückungsrente nicht erfüllt, weil er nicht während der letzten sieben Jahre vor dem Leistungsbezug in einem Betrieb gemäss Geltungsbereich des GAV FAR gearbeitet hat. Der Ausschuss Rekurse bestätigte mit Entscheid vom 17. April 2009 die Ablehnung des Leistungsgesuches.
B. Die am 6. Mai 2009 gegen die Stiftung FAR erhobene Klage des Z._ wies das Sozialversicherungsgericht des Kantons Zürich mit Entscheid vom 22. Dezember 2009 ab.
C. Z._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit den Rechtsbegehren, der Entscheid vom 22. Dezember 2009 sei aufzuheben und es sei ihm die vollumfängliche reglementarische Überbrückungsrente auszurichten, eventualiter sei die Sache zwecks Überprüfung des Sachverhalts an die Vorinstanz zurückzuweisen.
Die Stiftung FAR schliesst auf Abweisung der Beschwerde, das kantonale Gericht und das Bundesamt für Sozialversicherungen verzichten auf eine Vernehmlassung.

Erwägungen:
1. 1.1 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht (<ref-law>).
1.2 Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2. 2.1 Voraussetzung für den Anspruch auf eine ordentliche Überbrückungsrente gemäss Art. 14 GAV FAR ist, dass dieser in räumlicher (Art. 1), betrieblicher (Art. 2) und persönlicher (Art. 3) Hinsicht anwendbar ist, was in einem Streit um Leistungsansprüche durch das dafür zuständige Berufsvorsorgegericht vorfrageweise zu überprüfen ist (vgl. <ref-ruling> E. 3.1 S. 630; Urteil 9C_614/2009 vom 28. Januar 2010 E. 1; Urteil 9C_211/2008 vom 7. Mai 2008, in: SZS 2008 S. 487).
2.2 Nach der allgemeinen Regel des <ref-law>, wonach derjenige das Vorhandensein einer Tatsache zu beweisen hat, der aus ihr Rechte ableiten will, liegt die Beweislast für den betrieblichen und persönlichen Geltungsbereich und somit die Anwendbarkeit des GAV FAR beim Beschwerdeführer.
3. Es ist unbestritten, dass der ehemalige Arbeitgeber des Beschwerdeführers, die Einzelunternehmung X._, nicht dem SBV angehört hat, weshalb der GAV FAR nicht vertraglich anwendbar ist. Ebenso ist zu Recht nicht mehr bestritten, dass der GAV FAR für die Betonbohr- und Betonschneideunternehmen, die Art. 2 Abs. 1 GAV FAR als eine besondere Kategorie neben den Hoch-, Tief-, Untertag- und Strassenbaufirmen bezeichnet, nicht als allgemeinverbindlich erklärt wurde (vgl. Art. 2 Abs. 1 lit. g GAV FAR und Art. 2 Abs. 4 lit. f des Bundesratsbeschlusses vom 5. Juni 2003 über die Allgemeinverbindlicherklärung des GAV FAR sowie den Entscheid des Bundesrates betreffend die Einsprache gemäss Art. 10 des Bundesgesetzes über die Allgemeinverbindlicherklärung von Gesamtarbeitsverträgen, mit welchem die Betonbohr- und Betonschneidbetriebe aus dem Geltungsbereich des Bundesratsbeschlusses ausgenommen worden sind). Somit ist einzig streitig, ob die Firma X._ zur Kategorie der Betonbohr- und Betonschneideunternehmen gehörte oder eine von der Allgemeinverbindlicherklärung umfasste Baufirma war.
4. 4.1 Beim GAV FAR handelt es sich um einen Branchenvertrag, weshalb ihm diejenigen Arbeitnehmer unterstehen, die in einem bestimmten Wirtschaftszweig tätig sind (Urteil 4C.45/2002 vom 11. Juli 2002 E. 2.1.1). Die Frage, welchem Wirtschaftszweig ein Unternehmen zuzurechnen ist, beantwortet sich nach der Tätigkeit, die ihm das Gepräge gibt; entscheidend ist nicht der Handelsregistereintrag, sondern die tatsächliche Tätigkeit. Wenn ein Unternehmen mehrere Betriebe umfasst, welche unterschiedlichen Branchen angehören oder wenn innerhalb ein und desselben Betriebes mehrere Teile bestehen, welche eine unterschiedliche Zuordnung rechtfertigen, weil sie eine genügende, auch nach aussen erkennbare Selbständigkeit aufweisen, können auf die einzelnen Teile des Unternehmens resp. Betriebes unterschiedliche Gesamtarbeitsverträge zur Anwendung gelangen. Somit ist das massgebliche Zuordnungskriterium bei einem Branchenvertrag die Art der Tätigkeit, die den Betrieb oder den selbständigen Betreibsteil prägt (<ref-ruling> E. 2.1 S. 13 mit weiteren Hinweisen; Urteil 9C_614/2009 E. 2).
4.2 Die Vorinstanz hat festgehalten, mit überwiegender Wahrscheinlichkeit sei davon auszugehen, dass die Einzelunternehmung X._ hauptsächlich in den Bereichen Betonbohren und Betonfräsen tätig war und somit gemäss Dispositiv Ziffer 2 des Bundesratsbeschlusses vom 5. Juni 2003 nicht unter die Allgemeinverbindlicherklärung des GAV FAR falle. Dies hat sie begründet mit dem Eintrag im Handelsregister des Kantons Zürich, wonach die Einzelunternehmung X._ die "Ausführung von Bohr- und Fräsearbeiten" zum Zweck hatte, der Tatsache, dass die Schweizerische Unfallversicherungsanstalt (SUVA) die Firma als Betonbohr- und Betonfräsebetrieb einstufte sowie dem Hinweis auf das Briefpapier, mit welchem sich die Einzelunternehmung X._ für "Betonbohren, Betonfräsen, Umbauten, Mauererarbeiten" empfahl. Unter Verweis auf den im Jahre 2003 über die Einzelunternehmung eröffneten Konkurs und das zwischenzeitliche Ableben von X._ verzichtete die Vorinstanz auf weitere Abklärungen betreffend die den Betrieb prägende Tätigkeit.
4.3 Nach der Rechtsprechung kann der Richter das Beweisverfahren schliessen, wenn er aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür in antizipierter Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 4a S. 211).
4.4 Der Beschwerdeführer macht geltend, sein ehemaliger Arbeitgeber habe diverse Tätigkeiten des Bauhauptgewerbes ausgeführt. Weil er bereits in seiner vorinstanzlichen Klageschrift - unter Anerbietung mehrerer Zeugen als Beweis - auf die Dienstleistungsvielfalt der Einzelunternehmung X._ hingewiesen hat, handelt es sich entgegen der Meinung der Beschwerdegegnerin dabei um kein Novum im Sinne von <ref-law> (E. 1.2).
4.5 Die Beschwerdegegnerin hat vorprozessual behauptet, Abklärungen hätten ergeben, dass die Einzelunternehmung X._ nicht zum betrieblichen Geltungsbereich des GAV FAR zählte. Diese Abklärungen hat sie mit Verweis auf nicht weiter erklärte "datenschutzrechtliche Gründe" indes nicht belegt. Genauso wenig hat sie im vorinstanzlichen Verfahren diesbezügliche Abklärungsergebnisse vorgelegt.
4.6 Die Zweckumschreibung im Handelsregister ist für sich allein rechtlich nicht ausschlaggebend (E. 4.1). Genauso wenig genügt das Briefpapier, das im Übrigen mit dem Hinweis auf "Betonbohren, Betonfräsen, Umbauten, Maurerarbeiten" den Tätigkeitsbereich der Einzelunternehmung X._ nicht schlüssig umschreibt, zumal X._ seine Firma beispielsweise im Arbeitszeugnis des Beschwerdeführers als "Bauunternehmung" betitelte und der Firmenstempel ebenfalls die Aufschrift "X._ Bauunternehmung" trug. Betreffend die Einstufung der Einzelunternehmung als Betonbohr- und Betonfräsebetrieb durch die SUVA hat sich die Vorinstanz einzig auf die nicht belegten Angaben der Beschwerdegegnerin abgestützt. Die vom Beschwerdeführer angerufenen Zeugen, ein Vertreter eines Bauplanungs- und Architekturbüros, mit welchem die Einzelunternehmung X._ zusammen gearbeitet hat, sowie der langjährige Mitarbeiter und Bruder des verstorbenen X._, scheinen indes geeignet, sachdienlich Auskunft zu geben. Weiter hätte die Vorinstanz in Anwendung der Untersuchungsmaxime (Art. 73 Abs. 2 BVG) beim Verband der Betonbohr- und Betonschneidefirmen nachfragen können, ob die Einzelunternehmung X._ dort Mitglied war.
4.7 Nach dem Gesagten hat das kantonale Gericht in unzulässiger antizipierter Beweiswürdigung seine Untersuchungspflicht verletzt, weshalb es weitere Abklärungen betreffend die die Einzelunternehmung X._ prägenden Tätigkeiten zu treffen hat.
5. Das Verfahren ist kostenpflichtig (Art. 65 Abs. 1 und Abs. 3 lit. b BGG). Dem Prozessausgang gemäss gehen die Gerichtskosten zu Lasten der Beschwerdegegnerin (<ref-law>). Der Beschwerdeführer hat entsprechend dem Umfang der Beschwerde Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird in dem Sinne gutgeheissen, als der Entscheid des Sozialversicherungsgerichts des Kantons Zürich vom 22. Dezember 2009 aufgehoben und die Sache an die Vorinstanz zurückgewiesen wird, damit sie, nach erfolgter Abklärung im Sinne der Erwägungen, über die Beschwerde neu entscheide.
2. Die Gerichtskosten von Fr. 500.- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2000.- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 3. Mai 2010
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Dormann