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. 