Sachverhalt:
A. Mit Eingabe vom 15. September 2008 beantragte X._ dem Friedensrichter des Kreises Frenkendorf, Y._ sei wegen Ehrverletzung zu verurteilen und zu verpflichten, ihm eine Genugtuung von Fr. 5'000.-- auszurichten. Er legte der Eingabe einen Bericht von Z._ bei, worin geschildert wird, dass sich Y._ im Rahmen einer Ausstellung über Fertighäuser am 15. Juni 2008 in ehrverletzender Weise über X._ geäussert habe. Am 10. November 2008 fand vor dem Friedensrichter eine Verhandlung statt. Dabei kam jedoch keine Einigung zu Stande.
Am 7. Januar 2009 wurden Z._ und W._ als Zeugen durch das Bezirksstatthalteramt Liestal befragt. In der Folge stellte die Staatsanwaltschaft Basel-Landschaft das Strafverfahren gegen Y._ mit Verfügung vom 17. Februar 2011 ein. Zur Begründung führte sie an, die Beschuldigte bestreite die Vorwürfe. Diese könnten nicht mit hinreichender Sicherheit nachgewiesen werden, da die Aussagen von Z._ von W._ nicht bestätigt worden seien, obwohl W._ beim fraglichen Gespräch ebenfalls anwesend gewesen sei.
Gegen die Verfügung der Staatsanwaltschaft erhob X._ Beschwerde. Mit Beschluss vom 26. April 2011 wies das Kantonsgericht Basel-Landschaft das Rechtsmittel ab.
B. Mit Beschwerde in Strafsachen an das Bundesgericht vom 29. Juni 2011 beantragt X._ im Wesentlichen, der Beschluss des Kantonsgerichts sei aufzuheben. Eventualiter sei die Staatsanwaltschaft anzuweisen, Anklage zu erheben. Subeventualiter sei die Sache an die Staatsanwaltschaft zurückzuweisen.
Das Kantonsgericht schliesst in seiner Vernehmlassung auf Abweisung der Beschwerde. Die Staatsanwaltschaft beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. In seiner Stellungnahme dazu hält der Beschwerdeführer im Wesentlichen an seinen Anträgen und Rechtsauffassungen fest. Die Beschwerdegegnerin beantragt in erster Linie, auf die Beschwerde sei nicht einzutreten, und in zweiter Linie, sie sei abzuweisen.

Erwägungen:
1. 1.1 Der angefochtene Entscheid betrifft die Einstellung einer Strafuntersuchung. Dagegen ist die Beschwerde in Strafsachen nach Art. 78 ff. BGG gegeben.
1.2 Die Einstellungsverfügung datiert vom 17. Februar 2011. Anwendbar ist deshalb die am 1. Januar 2011 in Kraft getretene Schweizerische Strafprozessordnung (StPO; SR 312.0; siehe Art. 453 f. StPO und <ref-ruling> E. 1.1 S. 221 mit Hinweisen).
1.3 Zur Beschwerde in Strafsachen ist nach Art. 81 Abs. 1 BGG berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen hat oder keine Möglichkeit zur Teilnahme erhalten hat (lit. a) und ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat (lit. b). Da der angefochtene Entscheid nach dem 31. Dezember 2010 datiert, beurteilt sich die Frage des rechtlich geschützten Interesses nach der am 1. Januar 2011 in Kraft getretenen Fassung von Art. 81 Abs. 1 lit. b BGG (Art. 132 Abs. 1 BGG). In Betracht fällt vorliegend einzig Art. 81 Abs. 1 lit. b Ziff. 5 BGG. Danach wird der Privatklägerschaft ein rechtlich geschütztes Interesse zuerkannt, wenn der angefochtene Entscheid sich auf die Beurteilung ihrer Zivilansprüche auswirken kann (<ref-ruling> E. 1.3.1 S. 247 f. mit Hinweisen). Der Beschwerdeführer hat am vorinstanzlichen Verfahren teilgenommen, und er hat bereits adhäsionsweise Zivilforderungen geltend gemacht. Er ist zur Beschwerde legitimiert.
1.4 Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist einzutreten.
2. 2.1 Der Beschwerdeführer rügt, die Beteiligung von Richterin Regina Schaub am angefochtenen Entscheid verstosse gegen seinen verfassungsmässigen Anspruch auf ein unabhängiges und unparteiisches Gericht (Art. 30 Abs. 1 BV). Regina Schaub sei vorsitzende Richterin am früheren Verfahrensgericht in Strafsachen gewesen und habe in dieser Funktion an einem Verfahren mitgewirkt, welches mit dem vorliegenden in Beziehung stehe.
2.2 Der Beschwerdeführer hat im vorinstanzlichen Verfahren kein Ausstandsbegehren gestellt, sondern erhebt den Vorwurf der Befangenheit erstmals im Verfahren vor Bundesgericht. Nach der bundesgerichtlichen Rechtsprechung wird gestützt auf den auch für die Privaten geltenden Grundsatz von Treu und Glauben und das Verbot des Rechtsmissbrauchs (Art. 5 Abs. 3 BV) verlangt, dass ein echter oder vermeintlicher Organmangel so früh wie möglich, d.h. nach dessen Kenntnis bei erster Gelegenheit, geltend gemacht wird. Es verstösst gegen Treu und Glauben, Einwände dieser Art erst im Rechtsmittelverfahren vorzubringen, wenn der Mangel schon vorher hätte festgestellt und gerügt werden können. Wer den Mangel nicht unverzüglich vorbringt, wenn er davon Kenntnis erhält, sondern sich stillschweigend auf ein Verfahren einlässt, verwirkt den Anspruch auf spätere Anrufung der vermeintlich verletzten Ausstandsbestimmungen (BGE 136 I 207 E. 3.4 S. 211; <ref-ruling> E. 4.3 S. 496 f.; je mit Hinweisen).
Die Geltendmachung von Ausstandsgründen setzt die Kenntnis der personellen Zusammensetzung des Gerichts voraus. Das verfassungsmässige Recht auf einen unabhängigen und unparteiischen Richter umfasst deshalb auch den Anspruch auf Bekanntgabe, welche Richter am Entscheid mitwirken. Das bedeutet indessen nicht, dass dem Rechtsuchenden die Namen der entscheidenden Richter ausdrücklich mitgeteilt werden müssen. Es genügt vielmehr, dass er die Namen aus einer allgemein zugänglichen Quelle (Staatskalender oder Internet) entnehmen kann. Nach der Rechtsprechung müssen die Parteien damit rechnen, dass das Gericht in seiner ordentlichen Besetzung tagen wird. Dies gilt nicht nur für anwaltlich vertretene Parteien, sondern auch für juristische Laien (Urteile 2C_164/2008 vom 28. Juli 2008 E. 3.1; 1P.63/1999 vom 15. Februar 1999 E. 2; je mit Hinweisen).
Die Zusammensetzung des Kantonsgerichts Basel-Landschaft bzw. dessen strafrechtlicher Abteilung ist auf der Homepage des Kantons Basel-Landschaft ersichtlich (siehe http://www.baselland.ch/kantonsgericht-htm.283238.0.html [besucht am 13. Februar 2012]). Regina Schaub ist dort aufgeführt. Aufgrund der beschränkten Anzahl der Richter in der Abteilung Strafrecht musste der Beschwerdeführer ernsthaft damit rechnen, dass sie als Richterin mitwirken würde (vgl. BGE <ref-ruling> E. 4.4 S. 497). Der angebliche Befangenheitsgrund hätte damit bereits im vorinstanzlichen Verfahren vorgebracht werden können. Indem der Beschwerdeführer dies unterliess, verwirkte er den Anspruch auf dessen Geltendmachung.
3. 3.1 Der Beschwerdeführer rügt, die Vorinstanz habe Art. 319 Abs. 1 lit. a StPO verletzt, indem sie die Verfahrenseinstellung durch die Staatsanwaltschaft schützte. Das Kantonsgericht führte diesbezüglich aus, die Beschuldigte habe die gegen sie erhobenen Vorwürfe bestritten. Der Beschwerdeführer habe sich seinerseits auf einen Bericht gestützt, den Z._ im Anschluss an die Begegnung mit der Beschuldigten vom 15. Juni 2008 auf Aufforderung hin und nicht aus Eigeninitiative verfasst habe. In einem E-Mail an den damaligen Vertreter des Beschwerdeführers habe Z._ zudem geschrieben, er werde auf keinen Fall eine Aussage vor Gericht machen. In der Zeugeneinvernahme vor dem Bezirksstatthalteramt Liestal vom 7. Januar 2008 habe Z._ seine im erwähnten Bericht festgehaltenen Äusserungen grösstenteils nicht erneut wiedergegeben, sondern nur jeweils auf Frage der Untersuchungsbeamtin hin bestätigt. W._ habe bei der Einvernahme am 7. Januar 2009 angegeben, er habe am 15. Juni 2008 die Fertighausausstellung zusammen mit Z._, dessen Mutter und V._ besucht. Er habe das Haus, in welchem die Beschuldigte gewesen sei, zuerst alleine aufgesucht und mit ihr ein sachliches Gespräch geführt. Er habe weiter angegeben, dass Z._, der später hinzugekommen sei, das Gespräch mit der Beschuldigten auf ihren Wohnort und ihre Nachbarschaft gelenkt habe. Die Beschuldigte habe dabei wohl erwähnt, dass es zwischenmenschliche Probleme zwischen ihr und X._ gebe, und offenbar sei über bereits ergriffene rechtliche Schritte diskutiert worden. W._ habe sich aber weder an ein konkretes ehrverletzendes Wort der Beschuldigten erinnern noch die konkret vorgeworfenen Äusserungen bestätigen können. Dabei seien die vorgeworfenen Äusserungen von einer Qualität, dass man sich ein halbes Jahr später noch an sie erinnern sollte. Für die Beurteilung der Glaubwürdigkeit von Z._ sei zudem bedeutsam, dass dieser offensichtlich davon ausgehe, der Beschwerdeführer pflege mit dem Lebenspartner seiner Mutter, V._, eine freundschaftliche Beziehung. Da die Glaubwürdigkeit des Belastungszeugen nicht bedeutend höher eingestuft werden könne als jene von W._ sowie der Beschuldigten und auch keine weiteren belastenden Beweise für die Tat hätten erhoben werden können, könne der Tatverdacht nicht als erhärtet bezeichnet werden.
3.2 Der Beschwerdeführer bringt im Wesentlichen vor, es sei abstrus, wenn bei der Beurteilung der Glaubwürdigkeit das Bestreiten einer beschuldigten Person einer unter Androhung von Strafe und vorgängiger Ermahnung zur Wahrheit erfolgten Zeugenaussage gleichgestellt werde. Zwischen der Aussage von Z._ und W._ bestünden zudem keine Widersprüche. Letzterer habe ausgesagt, er habe nicht genau zugehört, weil ihn das alles gar nicht interessiert habe, er könne sich nicht an Details erinnern, den Sachverhalt aber dem Sinne nach bestätigen.
3.3 Gemäss Art. 319 Abs. 1 StPO verfügt die Staatsanwaltschaft unter anderem dann die Einstellung des Verfahrens, wenn kein Tatverdacht erhärtet ist, der eine Anklage rechtfertigt (lit. a) oder kein Straftatbestand erfüllt ist (lit. b). Aus dieser Bestimmung und aus Art. 324 Abs. 1 StPO ergibt sich der Grundsatz "im Zweifel für die Anklageerhebung" bzw. "in dubio pro duriore". Danach darf eine Einstellung durch die Staatsanwaltschaft nur bei klarer Straflosigkeit bzw. offensichtlich fehlenden Prozessvoraussetzungen verfügt werden. In Zweifelsfällen hat hingegen eine Anklage und gerichtliche Beurteilung zu erfolgen (sofern der Fall nicht mit Strafbefehl bzw. Strafverfügung erledigt werden kann; <ref-ruling> E. 7.1 f. S. 226 f.; Urteil 1B_1/2011 vom 20. April 2011 E. 4; je mit Hinweisen).
3.4 In der Einvernahme vom 7. Januar 2009 wurden Z._ die angeblichen Äusserungen von Y._ vorgetragen, wie er sie in seinem Bericht festgehalten hatte. Er wurde unter anderem gefragt, ob er sich an die Äusserungen von Y._ erinnern könne, dass X._ ein Betrüger sei, dass er in seiner Funktion als Fertighausvertreter und Architekt Leute über den Tisch ziehe und dass er Kaffeesatz und Knochen auf ihrem Grundstück entsorgt habe. Z._ bestätigte diese und andere Äusserungen. Dass er, wie die Vorinstanz festhielt, den Inhalt seines Berichts grösstenteils nicht erneut wiedergegeben hat, sondern nur jeweils auf Frage hin bestätigte, war offensichtlich durch die Art der Befragung bedingt und tut nichts zur Sache.
W._ wurde ebenfalls am 7. Januar 2009 einvernommen und nach den selben behaupteten Äusserungen gefragt. Er erklärte allgemein, es sei zu lange her, um sich an ein konkretes Wort von Y._ erinnern zu können. Mit den einzelnen Äusserungen konfrontiert, antworte er jeweils in ähnlicher Weise: "Es sind Sachen gesagt worden. Aber was?" - "Ich kann nicht sagen, ob Frau Y._ das Wort 'Betrüger' genannt hat." - "Es wurde viel geredet. Es kann sein, dass sie das gesagt hat." - "Mich hat das Gespräch nicht interessiert." - "Weil so viel geredet worden ist, bin ich mir nicht sicher, ob sie das gesagt hat." - "Es wurde viel geredet. Es kann sein, dass sie das gesagt hat. Aber ich bin nicht sicher. Es sind Anschuldigungen über den Architekten passiert." - "Ich weiss es nicht. Ich will nichts sagen, das mir angelastet werden kann."
Die Antworten von W._ sind charakteristisch für jemanden, der sich an eine Begebenheit nur noch vage erinnert. Dabei ist durchaus plausibel, dass sich jemand, den ein bestimmtes Gespräch nicht persönlich berührt und der davon eigentlich auch gar nichts wissen will, nach mehr als einem halben Jahr kaum mehr an konkrete Details zu erinnern vermag. Es ist indessen ein fundamentaler Unterschied, ob zwischen den Aussagen von zwei Zeugen Widersprüche aufscheinen oder ob einer der Zeugen sich aus plausiblen Gründen nicht mehr an Einzelheiten erinnert. Schon aus diesem Grund geht es nicht an, die Aussage von Z._ anhand jener von W._ in Frage zu stellen.
Grundsätzlich kann eine Anklage auch gestützt auf ein Einzelzeugnis erfolgen, zumal wenn dieses von einem glaubwürdigen Zeugen stammt (NATHAN LANDSHUT, in: Kommentar zur Schweizerischen Strafprozessordnung [StPO], 2010, N. 17 zu Art. 319 StPO). Diesbezüglich erwog die Vorinstanz, bei der Beurteilung der Glaubwürdigkeit von Z._ sei zu beachten, dass dieser offensichtlich davon ausgehe, der Beschwerdeführer pflege mit dem Lebenspartner seiner Mutter eine freundschaftliche Beziehung. Dass solche Umstände bei der Beurteilung der Glaubwürdigkeit eines Zeugen mitzubedenken sind, liegt auf der Hand, sie können jedoch nicht a priori entscheidend sein.
Insgesamt kann nicht von einem klaren Fall von Straflosigkeit gesprochen werden. Im Ergebnis hat die Vorinstanz vielmehr in unzulässiger Weise den Entscheid in der Sache vorweggenommen. Dies ist insbesondere Folge des Umstands, dass sie fälschlicherweise davon ausging, die Aussagen von Z._ und W._ würden sich im Kern widersprechen. Bedeutsam ist jedoch auch, dass sie zu Unrecht wohl die Glaubwürdigkeit der Beschuldigten in ihre Abwägung miteinbezog, den Beschwerdeführer selbst jedoch in dieser Hinsicht völlig ausblendete. Zudem hätte die Vorinstanz sogar dann, wenn man von einem Widerspruch in den Aussagen der beiden Zeugen hätte ausgehen können, nicht verlangen dürfen, dass die Glaubwürdigkeit des Belastungszeugen "bedeutend höher" sei als jene des zweiten Zeugen und der Beschuldigten.
4. Die Beschwerde ist gutzuheissen und der angefochtene Entscheid aufzuheben. Die Angelegenheit wird zur Fortführung des Strafverfahrens an die Staatsanwaltschaft Basel-Landschaft zurückgewiesen. Bei diesem Verfahrensausgang erübrigt es sich, auf die weiteren Rügen, welche der Beschwerdeführer in seiner Beschwerde vorträgt, einzugehen.
Die Vorinstanz hat dem Beschwerdeführer Gerichtskosten in der Höhe von Fr. 1'000.-- auferlegt. Parteientschädigungen hat sie nicht zugesprochen. Nach dem Gesagten hätte die Beschwerde gutgeheissen werden müssen, was bei der Kostenregelung zu berücksichtigen gewesen wäre. Es rechtfertigt sich, die Kosten des vorinstanzlichen Verfahrens dem Kanton Basel-Landschaft zu belasten (Art. 428 Abs. 4 StPO; Art. 67 StPO). Dies wird durch die Aufhebung des angefochtenen Entscheids bewirkt. Der Beschwerdeführer war im vorinstanzlichen Verfahren nicht anwaltlich vertreten. Es ist ihm deshalb für jenes Verfahren keine Parteientschädigung auszurichten. Auch insofern sind keine über die Aufhebung des angefochtenen Entscheids hinausgehenden Anordnungen zu treffen (Art. 68 Abs. 5 BGG).
Die Gerichtskosten des bundesgerichtlichen Verfahrens sind der unterliegenden Beschwerdegegnerin aufzuerlegen (Art. 66 Abs. 1 BGG). Sie hat dem obsiegenden, anwaltlich vertretenen Beschwerdeführer eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Beschluss vom 26. April 2011 des Kantonsgerichts Basel-Landschaft aufgehoben. Die Angelegenheit wird zur Fortführung des Strafverfahrens an die Staatsanwaltschaft Basel-Landschaft zurückgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat dem Beschwerdeführer eine Parteientschädigung von Fr. 1'500.-- auszurichten.
4. Dieses Urteil wird den Parteien, der Staatsanwaltschaft Basel-Landschaft und dem Kantonsgericht Basel-Landschaft, Abteilung Strafrecht, schriftlich mitgeteilt.
Lausanne, 24. Februar 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold