Sachverhalt:
A. Die A._ AG verfügte über ein bis zum 31. Dezember 2008 befristetes Recht zum Abbau von Sand, Kies und Steinen im Vierwaldstättersee vor Stansstad. Am 22. Februar 2005 ersuchte sie unter anderem um Erneuerung des Rechts zur Kiesausbeutung, um Erweiterung des Abbauperimeters, um Verleihung des Rechts zur Aufschüttung/Renaturierung eines Gebiets im Alpnachersee (neue Flachwasserzone) sowie um Baubewilligung für die einzelnen Teilprojekte. Das Gesuch mit Umweltverträglichkeitsbericht wurde am 5. Oktober 2005 öffentlich aufgelegt. X._, die Stockwerkeigentümergemeinschaften Y._ und Z._ sowie die B._ AG erhoben Einsprache gegen das Vorhaben.
In der ersten Hälfte 2007 nahm die A._ AG verschiedene Projektanpassungen vor, dies namentlich auch aufgrund einer Begutachtung des Vorhabens durch die Eidgenössische Natur- und Heimatschutzkommission (ENHK) und die Eidgenössische Kommission für Denkmalpflege (EKD).
Mit Beschluss vom 21. August 2007 wies der Regierungsrat des Kantons Nidwalden die Einsprache ab. Er erteilte gleichzeitig die Bewilligung zur Ausbeutung von Kies, Sand und andern Materialien nach <ref-law> (SR 814.20), die Verleihung zum Bezug von Steinen, Kies und Sand aus dem Seegebiet vor Stansstad nach Art. 26 Abs. 1 Ziff. 2 des kantonalen Wasserrechtsgesetzes vom 30. April 1967 (WRG/NW) sowie die Verleihung zum Wasserbezug aus dem Vierwaldstättersee nach <ref-law>/NW, dies für die Zeit vom 1. Januar 2008 bis zum 31. Dezember 2019. Sodann wurden Aufschüttungs- und Renaturierungsmassnahmen im Alpnachersee bewilligt und verschiedene Bedingungen und Auflagen angeordnet.
Gegen diese Beschlüsse des Regierungsrats erhoben die Einsprecher am 17. September 2007 Verwaltungsgerichtsbeschwerde an das Verwaltungsgericht des Kantons Nidwalden, welches mit Urteil vom 23. Juni 2008 auf die Beschwerde wegen fehlender Legitimation der Beschwerdeführer nicht eintrat. Mit Urteil 1C_26/2009 vom 27. Februar 2009 entschied das Bundesgericht auf Beschwerde der unterlegenen Einsprecher hin, das Verwaltungsgericht habe die Beschwerdeberechtigung zu Unrecht verneint. Es hob deshalb das Urteil des Verwaltungsgerichts vom 23. Juni 2008 auf und wies die Angelegenheit zur materiellen Prüfung der Beschwerde vom 17. September 2007 an die Vorinstanz zurück.
B. Am 11. März 2009 beantragte die A._ AG beim Verwaltungsgericht im Wesentlichen, der Verwaltungsgerichtsbeschwerde gegen ihr Vorhaben sei die aufschiebende Wirkung zu entziehen, damit sie bis zum Abschluss des gerichtlichen Verfahrens den Kiesabbau weiterführen könne. Mit Urteil vom 5. Juni 2009 hiess der Präsident des Verwaltungsgerichts den Antrag um Entzug der aufschiebenden Wirkung gut.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 10. Juli 2009 stellen X._ sowie die Stockwerkeigentümergemeinschaften Y._ und Z._ den Antrag, das Urteil des Präsidenten des Verwaltungsgerichts vom 5. Juni 2009 sei aufzuheben und der gewährte Entzug der aufschiebenden Wirkung sei zu beseitigen. Eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Das Verwaltungsgericht und der Regierungsrat verzichten unter Verweisung auf den angefochtenen Entscheid auf eine Vernehmlassung. Die A._ AG beantragt, auf die Beschwerde sei nicht einzutreten.

Erwägungen:
1. 1.1 Angefochten ist ein kantonal letztinstanzlicher Entscheid über den Entzug der aufschiebenden Wirkung in einem kantonalen Beschwerdeverfahren betreffend die Konzessionierung und Bewilligung der Kiesausbeutung. Es handelt sich dabei um eine Angelegenheit des öffentlichen Rechts (<ref-law>). Ein Ausschlussgrund nach <ref-law> liegt nicht vor. Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen und sind zur Beschwerde berechtigt (<ref-law>; Urteil des Bundesgerichts 1C_26/2009 vom 27. Februar 2009).
1.2 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist grundsätzlich nur gegen verfahrensabschliessende (End-)Entscheide zulässig (vgl. <ref-law>). Gegen selbstständig eröffnete Vor- und Zwischenentscheide, welche weder die Zuständigkeit noch ein Ausstandsbegehren betreffen, steht sie bloss offen, wenn der angefochtene Entscheid einen nicht wieder gutzumachenden Nachteil zur Folge hat (<ref-law>) oder die Gutheissung der Beschwerde sofort einen Entscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen kann (<ref-law>).
Die Eintretensvoraussetzungen von <ref-law> sollen das Bundesgericht entlasten. Dieses soll sich möglichst nur einmal mit einer Sache befassen und sich überdies nicht bereits in einem frühen Verfahrensstadium ohne genügend umfassende Sachverhaltskenntnis teilweise materiell festlegen müssen. Können allfällige Nachteile in verhältnismässiger Weise auch noch mit einer bundesgerichtlichen Beurteilung nach Ausfällung des Endentscheids behoben werden, so tritt das Bundesgericht auf gegen Vor- und Zwischenentscheide gerichtete Beschwerden nicht ein (<ref-ruling> E. 1.3.2 S. 34 f.).
Im umstrittenen Zwischenentscheid hat der Präsident des Verwaltungsgerichts das Gesuch der Beschwerdegegnerin, der Beschwerde die aufschiebende Wirkung zu entziehen, gutgeheissen. Mit dem bundesgerichtlichen Entscheid darüber, ob dies in Verletzung von Bundes(verfassungs)recht geschehen ist, kann weder das vorinstanzliche Verfahren abgeschlossen noch ein bedeutender Aufwand an Zeit oder Kosten erspart werden. Die Beschwerden sind deshalb nur zulässig, falls den Beschwerdeführern aus dem angefochtenen Zwischenentscheid ein nicht wieder gutzumachender Nachteil erwächst, d.h. damit eine Beeinträchtigung verbunden ist, die auch durch einen für sie allenfalls günstigen bundesgerichtlichen Endentscheid nicht oder nicht mehr vollständig behoben werden kann (<ref-ruling> E. 2.1; <ref-ruling> E. 2.3 S. 632; <ref-ruling> E. 4 S. 141). Ein solcher Nachteil liegt nicht schon darin, dass durch den Zwischenentscheid das vorinstanzliche Verfahren verlängert oder verteuert wird (vgl. <ref-ruling> E. 1.3.4 S. 36; <ref-ruling> E. 1c S. 100).
Der angefochtene Entscheid hat zur Folge, dass der umstrittene Kiesabbau mit einem Schwimmbagger im Vierwaldstättersee vor den Liegenschaften der Beschwerdeführer während dem hängigen verwaltungsgerichtlichen Beschwerdeverfahren weitergeführt wird. Die Beschwerdeführer berufen sich insbesondere auf unzulässige Lärmimmissionen und Erschütterungen, die mit dem Kiesabbau verbunden sind. Zudem machen sie unter Hinweis auf das Gutachten der ENHK und der EKD einen massiven Eingriff in den Seegrund geltend, der ökologisch wertvolle Flachwasserzonen zerstöre. Inwieweit der Abbau während der Hängigkeit des verwaltungsgerichtlichen Verfahrens geeignet ist, die Flachwasserzonen zu beeinträchtigen, ist den zur Verfügung stehenden Akten nicht zu entnehmen. Indessen ergibt sich aus E. 2.4 des Urteils des Bundesgerichts 1C_26/2009 vom 27. Februar 2009, welches dieselbe Angelegenheit betrifft, dass die Kiesentnahme mit dem Schwimmbagger zu den umstrittenen Lärmimmissionen auf den Grundstücken der Beschwerdeführer führt. Zumindest diese Beeinträchtigungen können durch einen für die Beschwerdeführer günstigen Endentscheid nicht mehr behoben werden. Damit liegt ein nicht wieder gutzumachender Nachteil im Sinne der Rechtsprechung vor. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde einzutreten.
2. Aus dem angefochtenen Entscheid ergibt sich, dass der Verwaltungsgerichtsbeschwerde nach § 72 Abs. 1 der kantonalen Verwaltungsrechtspflegeverordnung vom 8. Februar 1985 (VRPV) unter dem Vorbehalt abweichender Bestimmungen aufschiebende Wirkung zukommt. Die Rechtsmittelinstanz oder ihr Vorsitzender kann von Amtes wegen oder auf Gesuch einer Partei die aufschiebende Wirkung gewähren oder aufheben (§ 72 Abs. 2 VRPV). Die Beschwerdeführer machen geltend, der Entzug der aufschiebenden Wirkung verstosse gegen das Willkürverbot (<ref-law>).
2.1 Nach kantonaler Praxis und bundesgerichtlicher Rechtsprechung beurteilt sich die Frage, ob die aufschiebende Wirkung einer Beschwerde im Einzelfall zu belassen oder zu entziehen sei, anhand einer Interessenabwägung. Es ist danach zu prüfen, ob die Gründe, welche für die sofortige Vollstreckbarkeit der Verfügung sprechen, gewichtiger sind als jene, die für die gegenteilige Lösung angeführt werden können. Dabei fällt der vermutliche Ausgang des Verfahrens grundsätzlich nur insoweit in Betracht, als die Aussichten eindeutig sind (vgl. <ref-ruling> E. 3 mit Hinweisen auf weitere Urteile). Im vorliegenden Zusammenhang ist zu beachten, dass der Aufschub des Vollzugs des unterinstanzlichen Entscheids im verwaltungsgerichtlichen Verfahren die Regel bildet (§ 72 Abs. 1 VRPV). Der Entscheid soll nur ausnahmsweise vorgängig vollzogen werden, wenn ein überwiegendes Interesse der gesuchstellenden Partei oder allenfalls ein öffentliches Interesse für das Wirksamwerden des Entscheids schon vor Abschluss des Rechtsmittelverfahrens spricht.
2.2 Im angefochtenen Entscheid wird zunächst festgehalten, dass keine eindeutige Aussage über den voraussichtlichen Ausgang des kantonalen Gerichtsverfahrens möglich ist. Im Rahmen der Interessenabwägung berücksichtigte der Präsident des Verwaltungsgerichts, dass der Betrieb des Abbaubaggers zu Beeinträchtigungen der Aussicht, Erschütterungen, Lärm- und Luftimmissionen, Wertverminderungen der Liegenschaften sowie Beeinträchtigungen der Bodenstabilität im Uferbereich führe. Diesen Interessen stünden die Interessen der Beschwerdegegnerin an der Weiterführung ihrer wirtschaftlichen Tätigkeit gegenüber. Die Beschwerdegegnerin berufe sich auf die volkswirtschaftliche Bedeutung des Kiesabbaus im Hinblick auf die Versorgung der Region mit dem geförderten Rohmaterial, die Interessen des Kantons betreffend Abbaugebühren und Steuern sowie die Gefährdung von sieben Arbeitsplätzen. Zudem entstünden ökologisch und ökonomisch unerwünschte zusätzliche Transporte, wenn das Material aus anderen Regionen geliefert werden müsste. Die nachteiligen Konsequenzen einer vorübergehenden Einstellung des Kiesabbaus seien für die Beschwerdegegnerin ungleich einschneidender als die von den Beschwerdeführern vorläufig weiterhin zu duldenden Einschränkungen bei einem Entzug der aufschiebenden Wirkung.
2.3 Diesen Erwägungen der Vorinstanz kann nicht gefolgt werden. Dem angefochtenen Entscheid ist zu entnehmen, dass die frühere Berechtigung der Beschwerdegegnerin zum Kiesabbau bis zum 31. Dezember 2008 befristet war. Über die Weiterführung der Abbautätigkeit liegt erst ein erstinstanzlicher Entscheid des Regierungsrats vom 21. August 2007 vor, welcher seit September 2007 beim Verwaltungsgericht angefochten ist. Nach § 72 VRPV ist in diesem Verfahren die aufschiebende Wirkung die Regel. Die wirtschaftlichen Gründe, welche nach Auffassung der Vorinstanz für den Entzug der aufschiebenden Wirkung sprechen sollen, sind Folge der späten Einreichung eines redimensionierten Projekts zwischen dem 26. Januar und dem 31. Mai 2007 durch die Beschwerdegegnerin und der Verzögerung des gerichtlichen Verfahrens wegen der Verneinung der Legitimation der Beschwerdeführer durch das Verwaltungsgericht. Wenn solche Verzögerungen, die im Bewilligungs- und Konzessionierungsverfahren regelmässig vorkommen können, zu gewissen wirtschaftlichen Nachteilen für die Projektierenden führen, ist dem grundsätzlich nicht mit dem Entzug der aufschiebenden Wirkung des zulässigen Rechtsmittels zu begegnen, wenn keine anderen namhaften Gründe für den ausnahmsweisen Entzug der aufschiebenden Wirkung vorliegen. Der Entzug der aufschiebenden Wirkung muss die Ausnahme bleiben, wie dies auch die Vorinstanz in E. 4.3 des angefochtenen Entscheids darlegt. Mit der Gewährung des Entzugs der aufschiebenden Wirkung aus den angeführten wirtschaftlichen Gründen, die in bau- und planungsrechtlichen Verfahren häufig vorliegen, wird dem Ausnahmecharakter dieser verfahrensrechtlichen Möglichkeit keine Beachtung geschenkt. Die gewichtigen Interessen der Beschwerdeführer, welche die Verzögerungen nicht zu vertreten haben, werden dabei den wirtschaftlichen Interessen der Beschwerdegegnerin in unhaltbarer Weise untergeordnet. Das ist mit dem Willkürverbot (<ref-law>) nicht vereinbar. Die Beschwerdegegnerin hätte durch ein früheres Einreichen eines Projekts, das den heimat- und denkmalschutzrechtlichen Anliegen Rechnung trägt, darauf hinwirken können, dass rechtzeitig ein rechtskräftiger Entscheid über die Weiterführung des Kiesabbaus vor Ablauf der früheren Konzession vorliegt.
3. Die vorliegende Beschwerde ist somit wegen Verletzung des Willkürverbots gutzuheissen und der angefochtene Zwischenentscheid aufzuheben, ohne dass auf die weiteren Rügen der Beschwerdeführer näher eingegangen werden müsste. Das Verwaltungsgericht wird die Sache innert angemessener Frist zu beurteilen haben (<ref-law>).
Bei diesem Ausgang des Verfahrens wird die private Beschwerdegegnerin kosten- und entschädigungspflichtig (Art. 66 und 68 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und das Urteil des Präsidenten des Verwaltungsgerichts des Kantons Nidwalden vom 5. Juni 2009 aufgehoben.
2. Die Gerichtskosten von Fr. 2'000.-- werden der A._ AG auferlegt.
3. Die A._ AG hat den Beschwerdeführern eine Parteientschädigung von insgesamt Fr. 3'000.-- zu bezahlen.
4. Dieses Urteil wird den Parteien sowie dem Regierungsrat und dem Verwaltungsgericht des Kantons Nidwalden schriftlich mitgeteilt.
Lausanne, 8. September 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Haag