Sachverhalt:
A. Im Nachgang zu einer Aktion der Gewerkschaft Bau und Industrie vom 10. Oktober 2002 stellte die Q._ AG gegen sämtliche Beteiligten Strafantrag wegen Nötigung (<ref-law>) und Hausfriedensbruch (<ref-law>). Gegen 67 Personen wurde daraufhin eine Strafuntersuchung eröffnet. Nachdem die Strafuntersuchung am 17. Oktober 2006 eingestellt, die Einstellungsverfügung im Rechtsmittelverfahren jedoch wieder aufgehoben worden war, erhob die Staatsanwaltschaft des Kantons Zug am 26. Januar 2009 Anklage beim Einzelrichter des Strafgerichts des Kantons Zug.
Mit Eingabe vom 6. Juli 2009 stellten die Beschuldigten A._, B._, C._, D._, E._, F._, G._, H._, J._, K._, L._, M._, N._, O._ und P._ ein Ausstandsbegehren gegen den amtierenden Einzelrichter des Strafgerichts, Stephan Dalcher. Das Strafgericht wies das Gesuch mit Entscheid vom 13. Juli 2009 ab. Eine gegen diesen Entscheid erhobene Beschwerde wies die Justizkommission der strafrechtlichen Kammer des Obergerichts des Kantons Zug mit Urteil vom 20. August 2009 ebenfalls ab.
B. Mit Beschwerde in Strafsachen an das Bundesgericht vom 24. September 2009 beantragen A._ und die weiteren bereits aufgeführten Personen im Wesentlichen, das Urteil der Justizkommission sei aufzuheben und es sei festzustellen, dass Strafrichter Stephan Dalcher in den Ausstand zu treten habe.
Die Justizkommission und die Q._ AG beantragen in ihrer jeweiligen Vernehmlassung die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Staatsanwaltschaft verzichtete auf eine Stellungnahme.

Erwägungen:
1. Das angefochtene Urteil der Justizkommission der strafrechtlichen Kammer des Obergerichts des Kantons Zug ist im Rahmen eines Strafverfahrens ergangen. Demnach fällt für die Anfechtung vor Bundesgericht die Beschwerde in Strafsachen gemäss <ref-law> in Betracht. Die Beschwerde ist nach <ref-law> zulässig. Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist einzutreten.
2. 2.1 Die Vorinstanz wies die bei ihr erhobene Beschwerde insbesondere deshalb ab, weil sie das von den Beschwerdeführern gestellte Ausstandsbegehren nach § 45 Abs. 1 des Gesetzes des Kantons Zug vom 3. Oktober 1940 über die Organisation der Gerichtsbehörden (BGS 161.1; im Folgenden: GOG) als verspätet ansah. Weiter stellte sie fest, dass das Ausstandsbegehren ohnehin abzuweisen gewesen wäre.
Die Beschwerdeführer bestreiten nicht, dass ihr Ausstandsbegehren verspätet gewesen wäre, wenn die Frage der rechtzeitigen Geltendmachung nach § 45 Abs. 1 GOG hätte beurteilt werden müssen. Doch genau dies stellen sie in Abrede. Nach ihrer Ansicht betrifft § 45 Abs. 1 GOG ausschliesslich Ablehnungsgründe. Ausstandsgründe würden dagegen von Abs. 2 dieser Bestimmung erfasst. Danach könne das Ausstandsgesuch in jedem Zeitpunkt des Verfahrens gestellt werden. Bereits aus dem Wortlaut der beiden Absätze gehe hervor, dass Ausstands- und Ablehnungsgründe diesbezüglich anders zu handhaben seien. Die Vorinstanz habe dies verkannt und § 45 GOG damit willkürlich ausgelegt.
2.2 § 41 GOG zählt die Gründe auf, deretwegen eine Gerichtsperson in den Ausstand tritt, § 42 GOG dagegen jene, aufgrund derer eine Gerichtsperson von den Parteien abgelehnt werden oder selbst in den Ausstand treten kann. Damit folgt das kantonale Gesetz der Unterteilung in zwingende Ausstandsgründe, welche von Amtes wegen zu beachten sind, und fakultative Ausstandsgründe (bzw. Ablehnungsgründe), die den Antrag einer Partei voraussetzen, sofern die Gerichtsperson nicht von sich aus in den Ausstand tritt. Die verfassungsrechtliche Garantie auf einen unparteiischen, unbefangenen und unvoreingenommenen Richter gemäss <ref-law> gebietet eine derartige Unterscheidung indessen nicht (vgl. zum Ganzen REGINA KIENER, Richterliche Unabhängigkeit, 2001, S. 349 f.). Das Bundesgerichtsgesetz sieht sie zum Beispiel nicht vor, sondern spricht in Art. 34 allgemein von "Ausstandsgründen" und in Art. 36 von "Ausstandsbegehren" (Botschaft vom 28. Februar 2001 zur Totalrevision der Bundesrechtspflege, BBl 2001 4291 Ziff. 4.1.2.3).
2.3 Die vorliegend umstrittene Bestimmung von § 45 GOG hat folgenden Wortlaut:
1 Die Partei, welche einen Untersuchungs- und Anklagebeamten oder eine Gerichtsperson ablehnen will, hat ihr Gesuch bei der nach § 46 zuständigen Behörde so rechtzeitig einzureichen, dass der Ersatzmann einberufen werden kann.
2 Das Ausstandsgesuch kann in jedem Zeitpunkt des Verfahrens gestellt werden.
3 Das Gesuch ist schriftlich einzureichen und zu begründen. Wo das nicht möglich ist, hat sich der Gesuchsteller auf die gewissenhafte Erklärung des Abzulehnenden zu beziehen.
4 Das Ausstandsgesuch ist dem Betroffenen zur Vernehmlassung zuzustellen.
5 Ein weiteres Beweisverfahren findet in der Regel nicht statt.
Die Justizkommission legte im angefochtenen Entscheid dar, § 45 GOG könne aufgrund seiner Systematik nicht so verstanden werden, dass in Abs. 1 die Ablehnungsgründe und in Abs. 2 die Ausstandsgründe geregelt würden. Vielmehr regle Abs. 1 sowohl die Ausstands- als auch die Ablehnungsgründe. Abs. 2 beziehe sich auf Abs. 1, weshalb Ausstands- und Ablehnungsgründe zwar in jedem Verfahrensstadium geltend gemacht werden könnten, dies aber im Sinne von Abs. 1 rechtzeitig zu geschehen habe.
2.4 § 45 GOG befindet sich im Abschnitt III des kantonalen Gesetzes über die Organisation der Gerichtsbehörden. Dieser Abschnitt trägt den Titel "Ausstand der Behörden". Wie der Titel selbst, so unterscheidet augenscheinlich auch § 45 GOG nicht scharf zwischen Ausstands- und Ablehnungsgründen. Dies wird auch aus Abs. 3 und 4 der Bestimmung klar. Träfe die Behauptung der Beschwerdeführer zu, so würden sich die Vorschriften über die Abfassung des Gesuchs nach Abs. 3 nur auf Ablehnungsgründe beziehen, wohingegen nach Abs. 4 ausschliesslich Ausstandsgesuche dem Betroffenen zur Vernehmlassung zuzustellen wären. Dies scheint jedoch kaum der Sinn des Gesetzes zu sein. Im Übrigen wäre es verfahrensrechtlich wenig zweckmässig, wenn eine Partei Ausstandsgründe nach Belieben geltend machen könnte, wann sie will. Die Auslegung durch die Vorinstanz, wonach auch Ausstandsgründe rechtzeitig im Sinne von § 45 Abs. 1 GOG geltend zu machen sind, erweist sich deshalb als nicht willkürlich. Sie liegt im Übrigen auf der Linie der bundesgerichtlichen Rechtsprechung zur verfassungs- und konventionsrechtlichen Garantie auf einen unparteiischen, unbefangenen und unvoreingenommenen Richter (<ref-law> und Art. 6 Ziff. 1 EMRK), wonach ein Organmangel nach Treu und Glauben so früh wie möglich geltend zu machen ist (<ref-ruling> E. 4.3.1 S. 21; <ref-ruling> E. 4.3 S. 496 f.; je mit Hinweisen).
2.5 Durfte die Vorinstanz somit willkürfrei davon ausgehen, dass das Vorbringen verspätet war, so kann offen bleiben, ob die Rüge der Beschwerdeführer, die Vorinstanz habe zu Unrecht einen Ausstandsgrund verneint, begründet ist.
3. Es folgt, dass die Beschwerde abzuweisen ist. Diesem Ausgang des bundesgerichtlichen Verfahrens entsprechend sind die Gerichtskosten den unterliegenden Beschwerdeführern aufzuerlegen (<ref-law>). Die Beschwerdeführer haben der obsiegenden, anwaltlich vertretenen Beschwerdegegnerin eine dem Aufwand entsprechende Parteientschädigung zu bezahlen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer werden unter solidarischer Haftbarkeit verpflichtet, der Beschwerdegegnerin Fr. 800.-- als Parteientschädigung zu bezahlen.
4. Dieses Urteil wird den Parteien, der Staatsanwaltschaft und dem Obergericht des Kantons Zug, Justizkommission, Strafrechtliche Kammer, schriftlich mitgeteilt.
Lausanne, 24. November 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold