Sachverhalt:
A. A._ (Beschwerdeführer) meldete am 25. Januar 1998 der Kantonspolizei des Kantons Tessin, dass ihm in der Nacht zwischen Mitternacht und vier Uhr morgens sein Auto gestohlen worden sei. Er informierte in der Folge ebenso die X._ Versicherungen (Beschwerdegegnerin) über den Verlust seines Autos.
B. Da die Beschwerdegegnerin ihre Leistungen verweigerte, belangte der Beschwerdeführer sie mit Eingabe vom 24. August 1998 auf Bezahlung von Fr. 30'200.-- nebst Zins beim Landgericht des Kantons Uri. Dieses wies mit Entscheid vom 13./21. Juni 2005 die Klage ab.
Gegen das Urteil des Landgerichts gelangte der Beschwerdeführer mit kantonaler Berufung an das Obergericht des Kantons Uri, zivilrechtliche Abteilung. Er stellte den Antrag, das angefochtene Urteil aufzuheben und die Klage vom 24. August 1998 gutzuheissen. Das Obergericht wies die Berufung am 12. November 2007 ab und bestätigte den Entscheid des Landgerichts.
C. Der Beschwerdeführer beantragt mit Beschwerde in Zivilsachen, das Urteil des Obergerichts vom 12. November 2007 aufzuheben und die Klage gutzuheissen. Eventuell sei der angefochtene Entscheid aufzuheben und die Sache an die Vorinstanz, subeventuell an die erste Instanz, zurückzuweisen.
Die Beschwerdegegnerin begehrt die Abweisung der Beschwerde und die Bestätigung des angefochtenen Urteils. Das Obergericht verzichtete auf eine Vernehmlassung.

Erwägungen:
1. 1.1 Mit Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, andernfalls wird darauf nicht eingetreten. In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht kann das Bundesgericht nur insofern prüfen, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 3.2).
1.2 Die Feststellung des Sachverhalts kann nur gerügt werden, 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 (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.2.2).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, kann sich nicht damit begnügen, den bestrittenen Feststellungen eigene tatsächliche Behauptungen gegenüberzustellen oder darzulegen, wie die Beweise seiner Ansicht nach zu würdigen gewesen wären. Vielmehr hat er klar und substantiiert aufzuzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (<ref-ruling> E. 1.4.3; <ref-ruling> E. 1.3, 393 E. 7.1 S. 398, 462 E. 2.4).
1.3 Willkür im Sinne von <ref-law> liegt nach ständiger Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre. Das Bundesgericht hebt einen kantonalen Entscheid wegen Willkür nur auf, wenn er offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgrundsatz zuwiderläuft. Willkür liegt zudem nur vor, wenn nicht bloss die Begründung eines Entscheids, sondern auch das Ergebnis unhaltbar ist (<ref-ruling> E. 2.1; <ref-ruling> E. 2 S. 61, 217 E. 2.1).
Zu beachten ist, dass dem Sachgericht im Bereich der Beweiswürdigung ein erheblicher Ermessensspielraum zusteht (<ref-ruling> E. 4b S. 40). Das Bundesgericht greift auf Beschwerde hin nur ein, wenn das Sachgericht sein Ermessen missbraucht, insbesondere offensichtlich unhaltbare Schlüsse zieht, erhebliche Beweise übersieht oder solche willkürlich ausser Acht lässt (vgl. <ref-ruling> E. 2.1; <ref-ruling> E. 2.1; <ref-ruling> E. 4b S. 40; <ref-ruling> E. 1b S. 30).
2. Die Vorinstanz verwies betreffend die beweisrechtlichen Besonderheiten bei Ansprüchen aus Versicherungsverträgen auf die entsprechenden erstinstanzlichen Erwägungen, wonach gemäss bundesgerichtlicher Rechtsprechung derjenige, der gegenüber dem Versicherer einen Anspruch erhebt, für den Eintritt des Versicherungsfalls behauptungs- und beweispflichtig sei. Dieser Beweis sei regelmässig mit Schwierigkeiten verbunden. Deshalb geniesse der beweispflichtige Anspruchsberechtigte insoweit eine Beweiserleichterung und genüge seiner Beweisführungspflicht, wenn er den Eintritt des Versicherungsfalls überwiegend wahrscheinlich zu machen vermöge. Gelinge es dem Versicherer im Rahmen des ihm zustehenden Gegenbeweises, an der Sachdarstellung des Anspruchsberechtigten erhebliche Zweifel zu wecken, so sei der Hauptbeweis des Anspruchsberechtigten gescheitert.
Die Vorinstanz erwog weiter, vorliegend sei insbesondere die Frage strittig, ob dem Beschwerdeführer, wie von ihm geltend gemacht, das Fahrzeug tatsächlich gestohlen worden sei oder ob - wie von der Beschwerdegegnerin behauptet - ein Diebstahl vorgetäuscht worden sei. Um unnötige Wiederholungen zu vermeiden, könne betreffend den Sachverhalt auf die zutreffenden Ausführungen im angefochtenen Entscheid verwiesen werden. Ergänzend und teilweise wiederholend sei angefügt, dass unter anderem die Feststellung des gerichtlichen Gutachters entscheidend sei, wonach die elektronische Wegfahrsperre, mit der das Fahrzeug des Beschwerdeführers ausgestattet gewesen sei, nicht so leicht habe überwunden werden können und ein gewaltsames Vorgehen nutzlos gewesen wäre. Deshalb bestünden lediglich die beiden Varianten, wonach das vermisste Auto entweder auf ein grösseres Fahrzeug verladen oder durch eine Drittperson, die vom Beschwerdeführer den Schlüssel und den Pager erhalten habe, entfernt worden sei. Das Verladen auf ein grösseres Fahrzeug hätte mit einem Kran stattfinden müssen, da das Auto nicht bewegt werden konnte. Selbst wenn zugunsten des Beschwerdeführers das Beweismass der überwiegenden Wahrscheinlichkeit auf die Grenze der Glaubhaftmachung herabgesetzt werde, gelinge dem Beschwerdeführer der Nachweis des Fahrzeugverlades nicht, da diese Variante überwiegend unglaubwürdiger erscheine als das Entfernen des Fahrzeugs mittels Schlüssel und Pager. Dafür spreche nicht zuletzt auch nach allgemeiner Lebenserfahrung, dass ein solcher Abtransport mittels Autotransporter und Kran auf dem Parkplatz des Nachtclubs sicherlich für entsprechende Aufmerksamkeit gesorgt hätte und deshalb von vermeintlichen Dieben wohl nicht so durchgeführt worden wäre, da sie damit das Risiko eingegangen wären, von Drittpersonen beobachtet zu werden. Der Beschwerdeführer habe nicht wie vorausgesetzt, mit überwiegender Wahrscheinlichkeit seine Version des Sachverhalts untermauern können. Vielmehr sei es der Beschwerdegegnerin gelungen, erhebliche Zweifel an der Sachverhaltsdarstellung des Beschwerdeführers zu wecken, so dass damit der Hauptbeweis gescheitert sei.
3. Die rechtlichen Ausführungen betreffend Beweismass und Beweislast werden vom Beschwerdeführer zu Recht nicht angefochten. Er rügt hingegen eine offensichtlich unrichtige bzw. willkürliche Sachverhaltsfeststellung.
Dabei vermag der Beschwerdeführer jedoch den Begründungsanforderungen nicht zu genügen (vgl. Erwägung 1). Er zeigt nicht klar und substantiiert auf, inwiefern die Feststellungen der Vorinstanz willkürlich wären. Statt dessen unterbreitet er dem Bundesgericht in appellatorischer Weise die eigene Sicht der Dinge. Er scheint dabei zu verkennen, dass das Bundesgericht auch nach der Einführung des Bundesgerichtsgesetzes keine letzte Appellationsinstanz ist, die von den Parteien mit vollkommenen Rechtsmitteln angerufen werden könnte (vgl. Botschaft zur Totalrevision der Bundesrechtspflege vom 28. Februar 2001, BBl 2001 S. 4342). Zudem übt er über weite Strecken unzulässige Kritik am erstinstanzlichen Urteil. So insbesondere, wenn er dem Gericht pauschal unterstellt, bei einer Person, deren Nachname auf -ic endet, automatisch davon auszugehen, dass diese den Diebstahl selbst ausgeführt habe. Mit den entsprechenden Vorbringen ist der Beschwerdeführer nicht zu hören.
4. Weiter rügt der Beschwerdeführer, die Vorinstanz habe das rechtliche Gehör verletzt (<ref-law>; Art. 6 EMRK).
4.1 Nach <ref-law> haben die Parteien Anspruch auf rechtliches Gehör. Dieser Anspruch stellt einen wichtigen Aspekt des allgemeinen Gebots des fairen Verfahrens gemäss <ref-law> und Art. 6 Ziff. 1 EMRK dar (BGE <ref-ruling>5 E. 4.1). Er dient einerseits der Sachaufklärung und garantiert anderseits den Parteien ein persönlichkeitsbezogenes Mitwirkungsrecht im Verfahren. Sie sollen sich vor Erlass des Entscheids zur Sache äussern, erhebliche Beweise beibringen, Einsicht in die Akten nehmen und an der Erhebung von Beweisen mitwirken oder sich zumindest zum Beweisergebnis äussern können, wenn dieses geeignet ist, den Entscheid zu beeinflussen (<ref-ruling> E. 2.2 S. 504 f.; <ref-ruling> E. 2b; <ref-ruling> E. 2a/aa S. 16; <ref-ruling> E. 3b S. 383).
4.2 Zum einen erblickt der Beschwerdeführer eine Gehörsverletzung darin, dass die Vorinstanz seine Anträge auf Einholung von Expertisen betreffend die Glaubwürdigkeit des Beschwerdeführers und des Zeugen B._ in willkürlicher Weise abgelehnt habe.
4.2.1 Aus dem Anspruch auf rechtliches Gehör folgt insbesondere, dass die Richter rechtzeitig und formrichtig angebotene Beweismittel grundsätzlich abzunehmen haben (<ref-ruling> E. 2; <ref-ruling> E. 4b S. 268 f.; <ref-ruling> E. 2b S. 162 mit Hinweisen).
4.2.2 Die Vorinstanz wies die Anträge auf Einholung von Glaubwürdigkeitsgutachten mit der Begründung ab, dass es sich dabei um neue Beweisanträge i.S.v. Art. 246 der Zivilprozessordnung des Kantons Uri vom 23. März 1994 (ZPO/UR) handle. Neue Beweisanträge seien nur zuzulassen, wenn die Partei glaubhaft dartue, dass sie diese im erstinstanzlichen Verfahren unverschuldet nicht habe vorbringen können. Da der Beschwerdeführer bereits im Rahmen des vorinstanzlichen Beweisverfahrens diese Expertisen hätte beantragen können, sei er mit den entsprechenden Anträgen im Berufungsverfahren nicht zu hören.
4.2.3 Durch die Abweisung der Einholung der beiden Glaubwürdigkeitsgutachten hat die Vorinstanz das rechtliche Gehör nicht verletzt. Insbesondere ist das Vorbringen des Beschwerdeführers, es habe nicht der geringste Anlass dazu bestanden, bereits vor erster Instanz davon auszugehen, dass das Gericht seine Glaubwürdigkeit oder diejenige irgendeines Zeugen verwerfe, nicht überzeugend. Die Glaubwürdigkeit des Beschwerdeführers war nämlich bereits vor dem Landgericht ein zentrales Thema. Die Beschwerdegegnerin führte namentlich in ihrer Klageantwort vom 26. Oktober 1998 aus, es sei unglaubwürdig, wenn der Beschwerdeführer behaupte, dass sein Auto gestohlen worden sei, und machte auf seine widersprüchlichen Aussagen aufmerksam. Ebenso musste der Beschwerdeführer davon ausgehen, dass das Gericht die Glaubwürdigkeit des Zeugen B._ bezweifeln könnte. Denn die Beschwerdegegnerin bestritt dessen Glaubwürdigkeit bereits in der Eingabe vom 9. Juli 1999 betreffend die Beweiseinreden. Dass die Vorinstanz <ref-law>/UR willkürlich angewandt hätte, zeigt der Beschwerdeführer im Weiteren nicht auf und ist nicht ersichtlich.
4.3 Zum anderen sieht der Beschwerdeführer eine Verletzung des rechtlichen Gehörs im Umstand, dass die Vorinstanz auf die Motive des erstinstanzlichen Urteils verweist, ohne sich mit seinen vorgebrachten Gründen auseinanderzusetzen. Er listet verschiedene Vorbringen auf, mit denen sich die Vorinstanz nicht befasst habe.
Auch mit dieser Rüge vermag der Beschwerdeführer keine Gehörsverletzung aufzuzeigen. Das rechtliche Gehör verlangt, dass das Gericht die Vorbringen des vom Entscheid in seiner Rechtsstellung Betroffenen auch tatsächlich hört, sorgfältig und ernsthaft prüft und in der Entscheidfindung berücksichtigt. Daraus folgt die grundsätzliche Pflicht des Gerichts, den Entscheid zu begründen. Die Begründung eines Entscheids muss so abgefasst sein, dass der Betroffene ihn gegebenenfalls sachgerecht anfechten kann. Die Begründung muss kurz die wesentlichen Überlegungen nennen, von denen sich das Gericht hat leiten lassen und auf die sich sein Entscheid stützt. Nicht erforderlich ist hingegen, dass sich der Entscheid mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt (<ref-ruling> E. 3.3 S. 445; <ref-ruling> E. 4.3 S. 540; <ref-ruling> E. 3.2 S. 236; <ref-ruling> E. 2b S. 102 f.; <ref-ruling> E. 2b). Diesen Anforderungen vermag der angefochtene Entscheid zu genügen, da sich aus der Begründung ergibt, dass sich die Vorinstanz mit der zentralen Frage, ob dem Beschwerdeführer sein Auto gestohlen wurde, eingehend auseinandergesetzt hat. Nach bundesgerichtlicher Rechtsprechung ist es zudem grundsätzlich zulässig, dass das angefochtene Urteil auf die Begründung des erstinstanzlichen Urteils verweist (<ref-ruling> E. 2c mit Hinweisen).
5. Der Beschwerdeführer rügt schliesslich, die Vorinstanz habe aufgrund der allgemeinen Lebenserfahrung "völlig falsch" erwogen, die Variante mit dem Verladen erscheine überwiegend unglaubwürdiger als das Entfernen des Fahrzeuges mittels Schlüssel und Pager. Diese Rüge beruht auf einem unzutreffenden Verständnis des angefochtenen Entscheids. Die Vorinstanz kam nämlich aufgrund einer umfassenden Beweiswürdigung und nicht aufgrund der allgemeinen Lebenserfahrung zu diesem Schluss.
Der zusätzliche Hinweis der Vorinstanz, wonach die Variante eines Abtransports mittels Kran von Dieben wegen der dadurch erzeugten Aufmerksamkeit nach allgemeiner Lebenserfahrung nicht gewählt worden wäre, ist nicht entscheidrelevant. Es erübrigt sich daher, auf die diesbezüglichen Vorbringen des Beschwerdeführers näher einzugehen.
6. Sofern der Beschwerdeführer eine Verletzung von <ref-law> rügt, da eine Rechtsverzögerung vorliege, kann darauf nicht eingetreten werden. Es trifft zwar zu, dass sich die Gerichtsbehörden des Kantons Uri mit der Bearbeitung des vorliegenden Falles Zeit liessen. Da jedoch zum jetzigen Zeitpunkt ein Urteil vorliegt, ist das Rechtsschutzinteresse an der Behandlung dieser Rüge dahingefallen.
7. Zusammenfassend sind die Beweiswürdigung und entsprechende Schlussfolgerung der Vorinstanz, dass es dem Beschwerdeführer nicht gelungen sei, den Eintritt des Versicherungsfalls überwiegend wahrscheinlich zu machen, bundesrechtlich nicht zu beanstanden und es liegt keine Gehörsverletzung vor. Die Beschwerde ist demnach abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Uri, zivilrechtliche Abteilung, schriftlich mitgeteilt.
Lausanne, 9. Juni 2008
Im Namen der I. zivilrechtlichen Abteilung des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Corboz Sommer