Sachverhalt:
A. Y._ ist Eigentümer des Hotels A._ auf Parzelle Nr. 620 in Samnaun-Compatsch. Am 18. Juni 2008 reichte er ein Baugesuch ein, welches die Erweiterung des zum Hotel gehörenden Restaurants und die Errichtung einer Stützmauer vorsieht. Dieses Baugesuch folgte auf ein früheres, welches Y._ infolge von Mängeln zurückgezogen hatte. Gegen das neue Baugesuch erhob X._ Einsprache. X._ ist Inhaber des Hotels B._ auf der benachbarten Parzelle Nr. 596. Am 2. September 2008 erging der Bau- und Einspracheentscheid der Gemeinde. Diese hiess die Einsprache teilweise gut und verfügte die Auflage, drei Parkplätze seien zu verschieben, um einen genügend breiten Durchgang zum Hoteleingang zu gewährleisten. Im Übrigen wies die Gemeinde die Einsprache ab und bewilligte das Baugesuch.
Gegen den Bau- und Einspracheentscheid der Gemeinde erhob X._ mit Schreiben vom 2. Oktober 2008 Beschwerde an das Verwaltungsgericht des Kantons Graubünden. Dieses wies das Rechtsmittel mit Urteil vom 24. Februar 2009 ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 20. April 2009 beantragt X._, das Urteil des Verwaltungsgerichts sei aufzuheben. Eventualiter sei die Angelegenheit zur Neubeurteilung an die Vorinstanz zurückzuweisen. X._ rügt in mehrfacher Hinsicht eine willkürliche Anwendung des Parkplatzreglements vom 12. Juli 1987 der Gemeinde Samnaun und der dazugehörigen Norm "SNV 640 603" der Vereinigung Schweizerischer Strassenfachleute (VSS) (im Folgenden: VSS-Norm). Zudem macht er eine Verletzung seines Anspruchs auf rechtliches Gehör geltend.
Die Gemeinde Samnaun, das Verwaltungsgericht des Kantons Graubünden und der Beschwerdegegner beantragen in ihrer jeweiligen Vernehmlassung, die Beschwerde sei abzuweisen bzw. sie sei abzuweisen, soweit darauf eingetreten werden könne. In seiner Replik hält der Beschwerdeführer im Wesentlichen an seinen Anträgen und Rechtsauffassungen fest.
Mit Schreiben vom 11. Mai 2009 stellte der Beschwerdeführer das Gesuch, der Beschwerde sei die aufschiebende Wirkung zu erteilen. Eventualiter sei ein Baustopp zu verfügen. Der Beschwerdegegner und die Gemeinde Samnaun beantragten, das Gesuch sei abzuweisen. Das Verwaltungsgericht liess sich nicht vernehmen. Mit Präsidialverfügung vom 25. Mai 2009 hat das Bundesgericht das Gesuch um aufschiebende Wirkung abgewiesen.

Erwägungen:
1. Dem angefochtenen Urteil des Verwaltungsgerichts liegt ein Beschwerdeverfahren über eine baurechtliche Bewilligung zu Grunde. Nach Art. 34 Abs. 1 RPG (SR 700) gelten für die Rechtsmittel an die Bundesbehörden die allgemeinen Bestimmungen über die Bundesrechtspflege (<ref-ruling> E. 2.1 S. 404 mit Hinweis). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> steht auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält keinen Ausschlussgrund (<ref-law>). Angefochten ist ein Entscheid einer letzten kantonalen Instanz (<ref-law>). Der Beschwerdeführer hat vor der Vorinstanz am Verfahren teilgenommen und ist durch deren Entscheid besonders berührt (Art. 89 Abs. 1 lit. a und b BGG). Als Eigentümer des direkt benachbarten Grundstücks hat er ein Interesse an der korrekten Anwendung der als verletzt gerügten Vorschriften des kommunalen Parkplatzreglements. Zudem macht er eine Verletzung des rechtlichen Gehörs, mithin eine formelle Rechtsverweigerung geltend. Somit hat er ein schutzwürdiges Interesse im Sinne von <ref-law> (<ref-ruling> E. 1.3.1 und 1.3.2 S. 252 f. mit Hinweisen). Auf seine Beschwerde ist grundsätzlich einzutreten.
2. 2.1 Der Beschwerdeführer rügt eine willkürliche Anwendung von Art. 24 des Parkplatzreglements. Nach Abs. 2 dieser Bestimmung kann der Pflichtige in Ausnahmefällen, sofern die Gemeinde in der entsprechenden Fraktion über die nötigen Parkplätze verfügt, pro fehlenden Parkplatz, höchstens jedoch 20 % der geforderten Pflichtparkplätze, mittels Ersatzabgabe von Fr. 7'000.-- je Parkplatz abgelten.
Das Verwaltungsgericht hielt fest, es sei unstreitig, dass für das Bauvorhaben 17 Pflichtparkplätze erforderlich seien. 20 % ergäben damit 3.4 Parkplätze. Dass die Gemeinde diese Zahl aufgerundet und eine Abgeltung für 4 Pflichtparkplätze erlaubt habe, sei zulässig, zumal in der näheren Umgebung des Restaurants zahlreiche öffentliche Parkplätze zur Verfügung stünden.
Der Beschwerdeführer hält diesen Entscheid aus zwei Gründen für unhaltbar. Zum einen liege aus arithmetischen Überlegungen eine Abrundung auf 3 Parkplätze näher. Zum andern entsprächen 4 Parkplätze einer Abgeltung im Umfange von 24 %, womit die Höchstgrenze von 20 % überschritten werde.
2.2 Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 3.1 S. 153; <ref-ruling> E. 3.1 S. 473 f.; je mit Hinweisen).
2.3 Dem Beschwerdeführer ist darin beizupflichten, dass mathematisch gesehen 3.4 auf 3 abzurunden wäre. Die Vorinstanz hielt jedoch einen strikt mathematischen Ansatz nicht für zwingend und schützte den Entscheid der Gemeinde. Darin liegt keine Willkür. Zu bedenken ist, dass es hier lediglich um die Frage geht, ob ein Pflichtparkplatz mehr oder weniger mit einer Ersatzabgabe abgegolten werden kann. Zudem knüpft Art. 24 Abs. 2 des Parkplatzreglements die Möglichkeit der Abgeltung generell an die Voraussetzung, dass die Gemeinde in der betroffenen Fraktion über die nötigen Parkplätze verfügt, was gemäss angefochtenem Entscheid klar zutrifft. Schliesslich wies die Gemeinde im Bau- und Einspracheentscheid darauf hin, dass sie auch bei der Ermittlung der Anzahl Pflichtparkplätze (vorliegend 17) immer aufrunde. Zu Recht argumentierte sie, dass sich das gleiche Vorgehen auch rechtfertige, wenn es um die Frage gehe, wie viele Pflichtparkplätze mittels Ersatzabgabe abgegolten werden dürfen. Insgesamt erweist sich die Rüge der Willkür deshalb als unbegründet.
3. 3.1 Der Beschwerdeführer ist der Ansicht, die Vorinstanz habe auch Art. 25 des Parkplatzreglements willkürlich angewendet. Abs. 1 dieser Bestimmung hat folgenden Wortlaut: "Bei sämtlichen Betrieben werden nur jene Parkplätze angerechnet, welche während der Betriebszeit nicht abgesperrt und ganzjährig benützt werden können." Anlässlich des Augenscheins vom 23. Februar 2009 sei festgestellt worden, dass auf Parkplatz Nr. 1 ein Klein-Pneulader mit Schneeschleuder parkiert war. Dieser sei zweifellos auf Dauer dort abgestellt worden. Der Beschwerdegegner habe denn auch zu Protokoll gegeben, dass das Fahrzeug während der Wintersaison für die Räumung der Parkplätze und der Zufahrt benützt werde.
Diesbezüglich führte die Vorinstanz aus, der Augenschein habe ergeben, dass sämtliche 13 Parkplätze geeignet seien, darauf Motorfahrzeuge - wozu auch Schneeschleudern gehörten - zu parkieren.
3.2 Der Beschwerdeführer rügt die vorinstanzliche Sachverhaltsfeststellung nicht. Im Übrigen behauptet er auch nicht, dass der Beschwerdegegner gesagt habe, der Parkplatz Nr. 1 sei (während der Wintersaison) dauernd mit einer Schneeschleuder belegt. Unter diesen Voraussetzungen ist vom vorinstanzlichen Urteil auszugehen, in welchem die vom Beschwerdeführer behauptete Tatsache keine Grundlage findet (<ref-law>). Mangels hinreichender Substanziierung ist deshalb auf die Rüge des Beschwerdeführers nicht einzutreten (<ref-law>). Damit kann offen bleiben, ob das dauernde oder saisonale Abstellen einer Schneeschleuder tatsächlich eine willkürliche Anwendung von Art. 25 Abs. 1 des Parkplatzreglements bedeutete, wie der Beschwerdeführer behauptet.
4. 4.1 Der Beschwerdeführer macht geltend, Parkplatz Nr. 5 könne nicht als Pflichtparkplatz angerechnet werden. Dies gehe aus Ziff. 8 und 9 der VSS-Norm hervor, welche gemäss Art. 20 Abs. 3 des Parkplatzreglements anwendbar sei. Danach sei ein Mindestabstand von 35 cm von einer angrenzenden Mauer erforderlich. Dieser sei vorliegend nicht eingehalten worden, weshalb sich der angefochtene Entscheid diesbezüglich als willkürlich erweise.
4.2 Wie der Beschwerdeführer in seiner Beschwerde an das Verwaltungsgericht ausführte, verhindert der Mindestabstand, dass beim Manövrieren und dem Öffnen einer Fahrzeugtüre an der Mauer oder dem Fahrzeug selbst Schäden entstehen, oder nicht mehr genügend Platz vorhanden ist, um eine Fahrzeugtüre überhaupt zu öffnen. Aus der zu Ziff. 9 der VSS-Norm gehörigen Abbildung 4a geht indessen hervor, dass diese Vorschrift von der Situation ausgeht, dass sich auf der Parkplatzseite, welche der Mauer abgewandt ist, unmittelbar weitere Parkplätze anschliessen. Dies trifft auf Parkplatz Nr. 5 nicht zu. Auf der Mauer abgewandten Seite dieses Parkplatzes steht ausreichend Raum zum Manövrieren und zum Öffnen einer Fahrzeugtüre zur Verfügung. Dass im vorinstanzlichen Entscheid auf den Abstand verzichtet wurde, ist damit nachvollziehbar. Die Rüge der Willkür erweist sich als unbegründet.
5. 5.1 Der Beschwerdeführer rügt in diesem Zusammenhang, das Verwaltungsgericht sei auf seine Beanstandungen bezüglich der Anrechenbarkeit von Parkplatz Nr. 5 nicht eingegangen. Dadurch sei sein Anspruch auf rechtliches Gehör verletzt worden.
5.2 Aus dem Anspruch auf rechtliches Gehör (<ref-law>) folgt unter anderem die grundsätzliche Pflicht der Behörden, ihren Entscheid zu begründen. Die Begründung muss so abgefasst sein, dass der Betroffene den Entscheid 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 mit Hinweisen).
Diesen Anforderungen wird der vorinstanzliche Entscheid, wenn auch nur knapp, gerecht. Das Verwaltungsgericht führte aus, sämtliche 13 Parkplätze seien geeignet, darauf Fahrzeuge abzustellen. Damit verneinte es - wenn auch in recht pauschaler Weise - dass bei Parkplatz Nr. 5 ein zusätzlicher Mindestabstand von der angrenzenden Mauer zu berücksichtigen sei. Aufgrund der einfachen Sach- und Rechtslage war es dem Beschwerdeführer (wie in E. 4 hiervor ersichtlich) möglich, den Entscheid der Vorinstanz sachgerecht anzufechten. Seine Rüge der Verletzung von <ref-law> erweist sich damit als unbegründet.
6. Zusammenfassend ergibt sich, dass die Beschwerde abzuweisen ist, soweit darauf eingetreten werden kann. Diesem Ausgang des Verfahrens entsprechend sind die Gerichtskosten dem unterliegenden Beschwerdeführer aufzuerlegen (<ref-law>). Der Beschwerdeführer hat dem obsiegenden, anwaltlich vertretenen Beschwerdegegner eine dem Aufwand entsprechende Parteientschädigung zu bezahlen (<ref-law>). Der Gemeinde Samnaun, die in ihrem amtlichen Wirkungskreis obsiegt hat, ist keine Parteientschädigung zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Gemeinde Samnaun und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 30. Oktober 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold