Sachverhalt:
A. Am 15. Januar 1997 erteilte die Baubehörde der Gemeinde Samnaun der X._ AG die Baubewilligung für den Neubau eines Ladens (Geschäftshaus Y._) auf dem Grundstück Nr. 61. Dabei anerkannte sie einen Ausnützungstransport von 600 m2 anrechenbarer Grundstückfläche (AGF) - entsprechend einer Bruttogeschossfläche (BGF) von 540 m2 - ab Parzelle Nr. 95 via die Parzellen Nr. 792 und Nr. 46 auf die Parzelle Nr. 61.
Am 14. Dezember 1998 erteilte die Baubehörde der Gemeinde Samnaun der X._ AG eine Baubewilligung für einen Umbau des Geschäftshauses Y._ auf dem Grundstück Nr. 61. Dabei stellte sie fest, dass die zulässige Ausnützung nicht überschritten sei. Nicht an die Ausnützungsziffer angerechnet wurde ein Sport- und Fitnessraum im Dachgeschoss. Mit Bauabnahmeverfügung vom 3. August 2000 verpflichtete die Baubehörde die X._ AG, den Fitnessraum entsprechend auszustatten.
B. Mit Baugesuch vom 28. November 2002 ersuchte die X._ AG um eine "Zweckänderung von Fitness in Dachraum Y._, AZ-Transfer zu Gunsten Parz. 61". Dem Gesuch beigelegt war eine Berechnung der Ausnützungsziffer für das ganze Grundstück; vorgesehen war, die zusätzlich benötigte anrechenbare Grundstückfläche von der Parzelle Nr. 92 auf die Parzelle Nr. 61 zu übertragen.
Dagegen erhoben A._, B._, C._ sowie D._ und E._ Einsprache. Die Baubehörde Samnaun erwog mit Bauentscheid vom 3. Juni 2003, eine Ausnützungsübertragung von der Parzelle Nr. 92 komme nicht in Frage, da diese nicht unmittelbar benachbart sei. Aus diesem Grund könne auch der 1997 angeordnete Ausnützungstransport von der Parzelle Nr. 95 nicht anerkannt werden. Möglich sei nur eine Ausnützungsübertragung ab der Parzelle Nr. 65. Zudem fehlten drei Parkplätze. Demgemäss hiess die Baubehörde die Einsprache teilweise gut und bewilligte die Zweckänderung unter der Bedingung, dass die X._ AG noch 1162.9 m2 AGF (entsprechend 1'046.61 m2 BGF) ab der Parzelle Nr. 65 beschaffe, und mit der Auflage, drei zusätzliche Parkplätze real nachzuweisen oder abzugelten.
C. Dagegen erhob die X._ AG am 20. Juni 2003 Rekurs beim Verwaltungsgericht des Kantons Graubünden und beantragte Aufhebung und Zurückweisung an die Vorinstanz zur Gewährung des rechtlichen Gehörs, eventuell die Aufhebung der Bedingung, soweit sie damit verpflichtet werde, mehr als 562.9 m2 AGF (entsprechend 506 m2 BGF) ab Parzelle Nr. 65 zu beschaffen.
Sodann erhoben A._, B._, C._ sowie D._ und E._ am 23. Juni 2003 Rekurs beim Verwaltungsgericht mit dem Antrag auf Verweigerung der Baubewilligung.
Das Verwaltungsgericht führte einen Augenschein durch und wies beide Rekurse mit getrennten Urteilen vom 30. Juni 2004 (R 03 57 und R 03 58) ab.
D. Die X._ AG erhob am 21. September 2004 staatsrechtliche Beschwerde (Verfahren 1P.537/2004) mit dem Antrag, das Urteil R 03 57 des Verwaltungsgerichts sei aufzuheben, soweit die Beschwerde abgewiesen und sie zur Zahlung von Gerichts- und Parteikosten verpflichtet wurde.
E. Ferner erhoben A._, B._, C._ sowie D._ und E._ am 1. Oktober 2004 staatsrechtliche Beschwerde (Verfahren 1P.561/2004) mit dem Antrag, das Urteil R 03 58 des Verwaltungsgerichts sei aufzuheben.
F. A._, B._, C._ und D._ teilen mit, dass sie auf eine Teilnahme am Verfahren 1P.537/2004 verzichten.
Die X._ AG beantragt im Verfahren 1P.561/2004, die Beschwerde abzuweisen, soweit darauf einzutreten sei.
Den gleichen Antrag stellen das Verwaltungsgericht und die Gemeinde Samnaun in beiden Verfahren.
In dem vom Bundesgericht angeordneten zweiten Schriftenwechsel halten die Parteien an ihren Stellungnahmen fest.

Das Bundesgericht zieht in Erwägung:
1. Die beiden Beschwerden betreffen den gleichen Streitgegenstand und die gleichen Personen. Es rechtfertigt sich daher, die beiden Verfahren zu vereinigen (Art. 40 OG i.V.m. <ref-law>).
2. Gegen die kantonal letztinstanzlichen, auf kantonales Recht gestützten Endentscheide ist grundsätzlich die staatsrechtliche Beschwerde ans Bundesgericht zulässig (Art. 84 und 86 Abs. 1 OG).
2.1 Die Beschwerdeführerin im Verfahren 1P.537/2004 ist als Eigentümerin und Bauherrin der streitigen Baute zur staatsrechtlichen Beschwerde legitimiert (Art. 88 OG). Die Beschwerdeführer im Verfahren 1P.561/2004 sind als Eigentümer bzw. Mieter benachbarter Parzellen legitimiert, mit staatsrechtlicher Beschwerde eine willkürliche Anwendung von Bauvorschriften zu rügen, die (auch) dem Schutz nachbarlicher Interessen dienen (Art. 88 OG; <ref-ruling> E. 2c S. 46). Dazu gehören auch Bestimmungen über die Ausnützungsziffern (<ref-ruling> E. 2d S. 47), deren willkürliche Anwendung die Beschwerdeführer rügen. Insoweit ist auf die Beschwerden einzutreten.
2.2 Die Beschwerdeführer im Verfahren 1P.561/2004 rügen zudem willkürliche Annahmen des Verwaltungsgerichts beim Parkplatznachweis.
Vorschriften über die minimale Parkplatzzahl dienen nach der bundesgerichtlichen Rechtsprechung nicht nachbarlichen, sondern öffentlichen Interessen, so dass die Nachbarn nicht legitimiert sind, die willkürliche Anwendung solcher Vorschriften zu rügen (<ref-ruling> E. 2b S. 74 f.; Urteil 1P.309/1994 vom 29. Dezember 1994, publ. in RDAF 1995 S. 162, E. 3a). Die Beschwerdeführer stellen diese Rechtsprechung für Samnaun in Frage, da sich grosse Touristenströme in das Dorf ergiessen und fehlende Parkplätze bei einem Einkaufszentrum regelmässig dazu führten, dass auf den Plätzen der Nachbarn parkiert werde.
Es kann offen bleiben, ob an der bisherigen bundesgerichtlichen Rechtsprechung festzuhalten ist. So oder so könnte nachbarschützend höchstens die Pflicht sein, Parkplätze real zu erstellen, nicht aber eine allfällige Pflicht, Ersatzabgaben zu leisten. Insoweit wäre die Beschwerde in jedem Fall unbegründet:
In der rechtskräftigen Baubewilligung vom 14. Dezember 1998 wurden 125 Parkplätze verlangt und deren 115 als nachgewiesen anerkannt, so dass noch zehn fehlten. Mit der Bauabnahmeverfügung vom 3. August 2000 wurde die Bauherrin verpflichtet, den Nachweis für 11 Plätze zu erbringen, da inzwischen 117 erstellte Plätze anerkannt wurden, aber 3 Plätze wieder weggefallen waren. Im jetzt streitigen Verfahren konnten diese rechtskräftigen Verfügungen nicht mehr in Frage gestellt werden. Verfahrensgegenstand konnte deshalb von vornherein höchstens der Nachweis für die noch fehlenden Plätze bilden. Diesen Nachweis erbrachte die Beschwerdegegnerin zusammen mit dem Baugesuch vom 28. November 2002. Aufgrund einer Nachzählung der Betten verlangte die Gemeinde im Bauentscheid vom 3. Juni 2003 einen Nachweis für insgesamt 129 Plätze, wovon noch 3 fehlten. Auch im Verfahren vor dem Verwaltungsgericht konnte somit höchstens noch die Differenz zwischen den rechtskräftig anerkannten 117 Plätzen und der erforderlichen Zahl von 129 Streitgegenstand bilden. Das Verwaltungsgericht hat ausgeführt, gemäss dem kommunalen Parkplatzreglement könnten bis zu 20 % der geforderten Parkplätze durch Ersatzabgaben ersetzt werden. Dies wird von den Beschwerdeführern nicht beanstandet. Selbst wenn sämtliche der höchstens 12 noch fehlenden Plätze nicht nachgewiesen wären, könnten diese ohne weiteres mit einer Ersatzabgabe abgegolten werden und müssten nicht real erstellt werden.
3. Zu prüfen sind zunächst die Rügen der Beschwerdeführerin im Verfahren 1P.537/04.
3.1 Es ist unbestritten, dass die vorgesehene Umnutzung des Dachraums die Bruttogeschossfläche des Gebäudes erhöht. Im Baugesuch ist die Beschwerdeführerin davon ausgegangen, sie könne - entsprechend der offenbar früher geübten Praxis der Gemeinde - die hierfür benötigte Grundstückfläche ab der Parzelle Nr. 92 übertragen, obwohl diese nicht direkt benachbart ist. Inzwischen hat die Gemeinde ihre Praxis geändert und lässt nun entsprechend dem Wortlaut von Art. 39 Abs. 2 des Baugesetzes der Gemeinde Samnaun vom 15. Juli 1985 (BG) einen Ausnützungstransport nur noch von unmittelbar benachbarten Grundstücken zu. Die Beschwerdeführerin anerkennt diese neue Praxis und ist bereit, einen Ausnützungstransport ab der unmittelbar benachbarten Parzelle Nr. 65 vorzunehmen. Sie ist aber der Meinung, dass mit der Baubewilligung vom 15. Januar 1997 ein Ausnützungstransport von 600 m2 AGF (entsprechend 540 m2 BGF) ab der (nicht unmittelbar benachbarten) Parzelle Nr. 95 (via die Parzellen Nr. 792 und 46) anerkannt worden sei, der auch heute anerkannt werden müsse.
Die Gemeinde und ihr folgend das Verwaltungsgericht haben demgegenüber die alte Praxis als rechtswidrig erachtet; der damals anerkannte Ausnützungstransport könne für ein neues Baugesuch nicht anerkannt werden. Da die Änderung zu einem zusätzlichen Bedarf an BGF führe, müsse der Baugesuchsteller den Nachweis erbringen, dass die Anforderungen betreffend Ausnützungsziffer (AZ) für das gesamte Grundstück eingehalten seien. Der im früheren Baugesuch fälschlicherweise bewilligte Ausnützungstransport ab der nicht unmittelbar benachbarten Parzelle Nr. 95 könne im Rahmen des neuen Gesuchs nicht berücksichtigt werden. Die Gemeinde habe somit von der Anrechnung der umstrittenen 600 m2 AGF ab der Parzelle Nr. 95 absehen dürfen.
3.2 Die Beschwerdeführerin erblickt darin eine Verletzung des Willkürverbots, des Grundsatzes von Treu und Glauben, der Rechtssicherheit und der Eigentumsgarantie; mit der Bewilligung von 1997 sei der streitige Ausnützungstransport ab Parzelle Nr. 95 rechtskräftig bewilligt worden und könne heute nicht mehr rückgängig gemacht werden. Sie beansprucht nicht, den 1997 bewilligten Ausnützungstransport für den heute streitigen Umbau benutzen zu können. Sie anerkennt im Gegenteil ausdrücklich, dass die damals übertragenen 600 m2 AGF bereits konsumiert sind. Sie anerkennt auch, dass sie für die zusätzlich beanspruchte anrechenbare Fläche einen zusätzlichen Ausnützungstransport sicherzustellen hat. Sie erachtet aber als willkürlich, dass sie heute den AZ-Nachweis für die ganze Baute erbringen müsse, also auch für diejenigen Bauteile, die früher aufgrund des damals anerkannten Ausnützungstransports rechtskräftig bewilligt wurden.
3.3 Die Gemeinde verfolgt die Praxis, dass eine Liegenschaft, die aufgrund einer früher akzeptierten fehlerhaften Ausnützungsberechnung übernutzt ist, umgebaut oder im Zwecke geändert werden kann, ohne dass die fehlende anrechenbare Grundstücksfläche nachgewiesen werden muss, solange der Umbau oder die Zweckänderung AZ-neutral ist oder gar AZ-pflichtige Bruttogeschossfläche aufgegeben wird. Diese Praxis ist vom Bundesgericht mit Urteil vom heutigen Tag zwischen den gleichen Parteien als willkürfrei beurteilt worden (Urteil 1P.487/2004). Sie hat zur Folge, dass auch bei einem späteren Umbau oder einer Umnutzung die früher (fälschlicherweise) akzeptierte Übernutzung nicht reduziert werden muss. Diese Praxis geht über die bundesverfassungsrechtliche Bestandesgarantie hinaus, ist aber jedenfalls verfassungsrechtlich nicht zu beanstanden. Sie muss alsdann rechtsgleich für alle Bauherrschaften angewendet werden.
3.4 Auf der Grundlage dieser Praxis lässt es sich nun sachlich nicht rechtfertigen, bei einem Baugesuch für eine zusätzliche Nutzfläche, die als solche durch einen zusätzlichen Ausnützungstransport abgedeckt ist, einen AZ-Nachweis über die ganze Liegenschaft zu verlangen.
Das Verwaltungsgericht und die Gemeinde argumentieren, diese Anforderung führe entgegen der Auffassung der Beschwerdeführerin nicht zu einem unzulässigen Widerruf der früher erteilten Baubewilligung: Diese könne uneingeschränkt genutzt werden; sie habe jedoch keine Bindungswirkung für eine neue Baubewilligung. Bei einer solchen sei es zulässig und im Lichte des Legalitätsprinzips geradezu geboten, vom Baugesuchsteller den AZ-Nachweis für das Ganze zu verlangen. Diese Argumentation müsste, wenn sie zuträfe, auch gelten, wenn ein bewilligungspflichtiger Umbau nicht zu einer Zunahme der anrechenbaren Geschossfläche führt. Auch dann steht nämlich eine neue Baubewilligung zur Diskussion, für welche die früher erteilten Bewilligungen keine Bindungswirkung haben könnten.
Entscheidend ist in beiden Fällen die Frage, ob anlässlich eines Umbauprojekts, welches nur einen Teil der Liegenschaft betrifft, nachträglich ein gesetzeskonformer AZ-Nachweis für die ganze Liegenschaft verlangt werden soll. Ob die Bruttogeschossfläche als solche unverändert bleibt, oder ob sie zunimmt, wobei diese Zunahme vollumfänglich durch einen rechtmässigen Ausnützungstransport abgedeckt ist, kann dafür nicht entscheidend sein. Entgegen der Darstellung der Gemeinde und des Verwaltungsgerichts entsteht nämlich auch im zweiten Fall nicht eine zusätzliche Übernutzung, sondern nur eine zusätzliche Ausnützung, die aber durch den zusätzlichen Ausnützungstransport abgedeckt ist. Die Übernutzung bzw. das Ausmass der Rechtswidrigkeit bleibt in beiden Fällen gleich. Wenn die Gemeinde im Falle einer AZ-neutralen Umbaute keinen AZ-Nachweis für die ganze Baute verlangt, mit dem Argument, das Mass der Rechtswidrigkeit werde nicht erhöht, dann muss dies auch im zweiten Fall gelten.
Im vorliegenden Fall hat die bestehende Baute - wenn man die AZ-Berechnung nach neuer Praxis der Gemeinde anwendet - rund 600 m2 BGF zu viel. Würde sie - was nach willkürfreier Auffassung der kantonalen Behörden zulässig wäre - ohne BGF-Zunahme umgebaut oder in ihrem Zweck geändert, hätte sie nach wie vor rund 600 m2 BGF zu viel. Das vorliegend streitige Bauprojekt benötigt eine zusätzliche BGF von rund 450 m2. Werden nun diese 450 m2 durch einen - auch nach neuer Praxis rechtmässigen - Ausnützungstransport abgedeckt, so hat nachher die gesamte Liegenschaft ebenfalls rund 600 m2 BGF zu viel. Es ist sachlich nicht begründbar, in diesem Fall vom Bauherrn einen nach neuer Praxis korrekten AZ-Nachweis für die ganze Liegenschaft zu verlangen, in jenem Fall aber nicht.
Die Willkürlichkeit einer solchen Anforderung ergibt sich noch klarer, wenn das Umbauprojekt nur minimal mehr Nutzfläche beanspruchte: Ein Umbauprojekt, bei welchem die Bruttogeschossfläche unverändert bleibt, wäre ohne zusätzlichen AZ-Nachweis zulässig. Würde aber durch ein Umbauprojekt nur ein einziger Quadratmeter BGF mehr beansprucht als bisher, müsste die Bauherrschaft einen zusätzlichen AZ-Nachweis für die gesamten rund 550 m2 erbringen. Dies ist unhaltbar: Entweder ist der AZ-Nachweis über die ganze Liegenschaft bei jedem Umbauprojekt zu erbringen, auch wenn die Bruttogeschossfläche nicht zunimmt, oder dann muss auch bei einem Umbauprojekt, welches zu einer zusätzlichen Bruttogeschossfläche führt, der AZ-Nachweis nur für diese zusätzliche Fläche erbracht werden.
3.5 Das Verwaltungsgericht und die Gemeinde beziehen sich auf das Verwaltungsgerichtsurteil R 02 133, wo entschieden wurde, dass ein Bauherr aus einer falschen Ausnützungsberechnung in einer früheren Baubewilligung keine verbindlichen Wirkungen für zukünftige Bauvorhaben ableiten könne. Wenn aber die Gemeinde und das Verwaltungsgericht bei einem AZ-neutralen Umbau in verfassungsrechtlich haltbarer Weise keinen AZ-Nachweis über die gesamte Baute verlangen, dann anerkennen sie im Ergebnis doch eine verbindliche Wirkung der früheren Baubewilligung auch für neue Vorhaben. Für einen nicht AZ-neutralen Umbau kann dann logischerweise nur für die zusätzliche Bruttogeschossfläche ein AZ-Nachweis verlangt werden.
Anders ist es selbstverständlich, wenn sich der Bauherr für die zusätzliche Bruttogeschossfläche auf eine angeblich bestehende Ausnützungsreserve beruft: In diesem Fall ist die Baubehörde berechtigt, einen vollständigen AZ-Nachweis für das gesamte Grundstück zu verlangen, um zu überprüfen, ob eine solche Reserve tatsächlich besteht. Dabei ist sie an Ausnützungsberechnungen in früheren Baubewilligungen nicht gebunden soweit diese nicht Niederschlag im Dispositiv der Bewilligung gefunden haben. Ansonsten wäre sie möglicherweise gezwungen, bei einem bereits übernutzten Grundstück eine zusätzliche Übernutzung zuzulassen, wodurch das Ausmass der Übernutzung und damit der Rechtswidrigkeit erhöht würde. Dies ist jedoch im vorliegenden Fall, wie oben (E. 3.4) dargelegt wurde, gerade nicht der Fall.
3.6 Im vorliegenden Falle kommt hinzu, dass der Ausnützungstransport von 600 m2 AGF (entsprechend 540 m2 BGF) ab Parzelle Nr. 95 in der Baubewilligung vom 15. Januar 1997 nicht etwa nur vorfrageweise akzeptiert, sondern im Dispositiv der Baubewilligung verbindlich zur Anmerkung im Grundbuch angeordnet worden ist. Wird nun anlässlich einer späteren Baubewilligung ein anderer AZ-Nachweis für die damals bewilligte Bruttogeschossfläche verlangt, so läuft dies im Ergebnis auf einen (teilweisen) Widerruf der damaligen Baubewilligung hinaus: Zwar muss die bestehende Baute nicht verändert werden, solange kein Umbaugesuch gestellt wird. Hingegen wird anlässlich eines Baugesuchs für ein Umbauprojekt (welches nur einen relativ kleinen Teil des gesamten Gebäudes betrifft) die Rechtmässigkeit der bestehenden Baute in Frage gestellt mit der Folge, dass das neue Gesuch nur bewilligt wird, wenn (auch) für die bestehende Baute entgegen der ausdrücklichen Anordnung des Ausnützungstransports in der rechtskräftigen Baubewilligung ein anderer AZ-Nachweis erbracht wird. Könnte dieser Nachweis nicht erbracht werden, hätte die Bauherrschaft nur die Wahl, entweder auf die neue Nutzung zu verzichten (obwohl dafür ein rechtsgenüglicher AZ-Nachweis vorliegt) oder entgegen der ausdrücklichen Anordnung des Ausnützungstransports in der damaligen Baubewilligung einen Teil der bisherigen Nutzung aufzugeben.
3.7 Die Beschwerde im Verfahren 1P.537/2004 erweist sich damit als begründet.
4. Zu prüfen sind im Folgenden die Rügen der Beschwerdeführer des Verfahrens 1P.561/2004.
4.1 Sie beanstanden willkürliche Annahmen zur Ausnützungsberechnung; diese Berechnung sei mangels genügender Pläne nicht überprüfbar. Das Verwaltungsgericht habe eine formelle Rechtsverweigerung begangen, indem es den Antrag, vermasste Pläne und Schnitte beizubringen, übergangen habe. Ausserdem seien willkürlich verschiedene Räume nicht angerechnet worden.
Nachdem - wie aus E. 3 hervorgeht - im Rahmen des Umnutzungsprojekts nicht ein AZ-Nachweis für das ganze Gebäude, sondern nur für die zusätzlich beanspruchte Fläche verlangt werden kann, erweisen sich diese Vorbringen von vornherein als unerheblich. Erforderlich ist nur ein AZ-Nachweis für die streitigen Räume (bisheriger Fitnessraum und Fläche im Dachgeschoss), deren Fläche nicht umstritten ist und für welche die Notwendigkeit eines Ausnützungstransports auch von der Bauherrin anerkannt ist.
4.2 Weiter rügen die Beschwerdeführer, es sei willkürlich, eine Baubewilligung mit der Auflage des Ausnützungstransports zu verfügen.
Indessen wird von den Beschwerdeführern nicht dargelegt, gegen welche Normen oder Rechtsgrundsätze dadurch verstossen werden soll. Entgegen der Darstellung der Beschwerdeführer hat die Behörde nicht die (formlose) Zusicherung eines Ausnützungstransports als ausreichend erachtet; sie hat vielmehr die Baubewilligung mit der (suspensiven) Bedingung verbunden, dass die fehlende Fläche im Rahmen einer Grunddienstbarkeit beschafft und diese Belastung im Grundbuch angemerkt wird. Solange dies nicht erfolgt ist, kann von der Baubewilligung kein Gebrauch gemacht werden. Auch werden dadurch die Rechte der Einsprecher nicht berührt: Diese haben die Möglichkeit, im Grundbuch nachzuprüfen, ob die angeordnete Bedingung tatsächlich erfüllt ist (<ref-law>), und gegebenenfalls die Wiederherstellung zu verlangen, wenn von der Baubewilligung Gebrauch gemacht wird, ohne dass die Bedingung erfüllt ist.
4.3 Die Beschwerdeführer rügen sodann einen Verstoss gegen das Gebot der Rechtsgleichheit, weil das Verwaltungsgericht im Entscheid R 02 64/66/67 vom 14. Januar 2003 eine ihnen erteilte Baubewilligung mangels Nachweises eines Ausnützungstransports aufgehoben habe. Soweit aus dem Urteilssachverhalt ersichtlich, wurde die damals streitige Baubewilligung jedoch von der Gemeinde gestützt auf das Hofstattrecht (Art. 6 BG) ohne die Auflage eines Ausnützungstransports erteilt, weshalb beide Sachverhalte nicht vergleichbar sind. Das Verwaltungsgericht durfte sich als Rechtsmittelinstanz mit der Aufhebung der Baubewilligung wegen Überschreitung der zulässigen Ausnützung begnügen, und musste nicht von Amtes wegen eine Auflage zum Ausnützungstransport verfügen.
5. Somit erweist sich die Beschwerde im Verfahren 1P.537/2004 als begründet, diejenige im Verfahren 1P.561/2004 als unbegründet, soweit darauf eingetreten werden kann.
5.1 Im Verfahren 1P.537/2004 haben die ursprünglichen Einsprecher und Rekurrenten auf eine Teilnahme am bundesgerichtlichen Verfahren verzichtet. Nach der bundesgerichtlichen Rechtsprechung kann sich zwar im Verfahren der Verwaltungsbeschwerde und der Verwaltungsgerichtsbeschwerde ein Baugesuchsteller, um dessen Vorhaben es im Verfahren geht, nicht seiner Kostenpflicht entziehen, indem er auf eine Antragstellung verzichtet. Denn solange der Projektant - wenn auch nur stillschweigend - an seinem Vorhaben festhält, bleibt er notwendigerweise Partei in einem Verfahren, welches dieses Vorhaben in Frage stellt (<ref-ruling> E. 2b S. 93 f. mit Hinweisen).
Anders verhält es sich aber, wenn ein ursprünglicher Einsprecher sich im Verfahren der staatsrechtlichen Beschwerde nicht mehr beteiligt. Die staatsrechtliche Beschwerde ist ein selbständiges Verfahren, in welchem einzig der letztinstanzliche kantonale Entscheid Anfechtungsobjekt ist. Der ursprüngliche Einsprecher ist nicht notwendigerweise Partei und kann auf eine Verfahrensbeteiligung und damit auch auf das Kostenrisiko verzichten. Für das Verfahren 1P.537/2004 sind daher keine Kosten zu erheben (Art. 156 Abs. 2 OG). Hingegen hat die unterliegende Gemeinde der Beschwerdeführerin die Parteikosten zu ersetzen (Art. 159 Abs. 2 OG).
5.2 Im Verfahren 1P.561/2004 tragen die unterliegenden Beschwerdeführer die Verfahrenskosten (Art. 156 Abs. 1 OG). Sie haben zudem der Beschwerdegegnerin und der Gemeinde Samnaun, welche als kleine Gemeinde ohne eigenen Rechtsdienst auf den Beizug eines Anwalts angewiesen war, die Parteikosten zu ersetzen (Art. 159 Abs. 1 und 2 OG).

Demnach erkennt das Bundesgericht :
1. Die Verfahren 1P.537/2004 und 1P.561/2004 werden vereinigt.
2. Die staatsrechtliche Beschwerde im Verfahren 1P.537/2004 wird gutgeheissen. Das Urteil R 03 57 des Verwaltungsgerichts des Kantons Graubünden vom 30. Juni 2004 wird aufgehoben.
3. Die staatsrechtliche Beschwerde im Verfahren 1P.561/2004 wird abgewiesen, soweit darauf einzutreten ist.
4. Für das Verfahren 1P.537/2004 werden keine Kosten erhoben.
5. Für das Verfahren 1P.561/2004 wird die Gerichtsgebühr von Fr. 4'000.-- den Beschwerdeführern auferlegt.
6. Die Gemeinde Samnaun hat die Beschwerdeführerin im Verfahren 1P.537/2004 für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
7. Die Beschwerdeführer im Verfahren 1P.561/2004 haben die Beschwerdegegnerin und die Gemeinde Samnaun für das bundesgerichtliche Verfahren mit je Fr. 3'000.-- zu entschädigen.
8. Dieses Urteil wird den Parteien, der Gemeinde Samnaun und dem Verwaltungsgericht des Kantons Graubünden, 4. Kammer, schriftlich mitgeteilt.
Lausanne, 6. Juni 2005
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: