Baueinsprache, Art. 9 und 29 BV,hat sich ergeben: A.- Die C._ Generalunternehmung, Tomils, reichte am 6. September 1994 bei der Gemeinde Cazis ein Baugesuch ein für die Errichtung von 3 Wohnhäusern im Weiler D._, Cazis. Das Gesuch wurde im Amtsblatt veröffentlicht mit dem Hinweis, dass öffentlichrechtliche Einsprachen an den Gemeindevorstand Cazis, privatrechtliche an das Kreisamt Thusis zu richten seien. H.A._ und J.A._ erhoben am 5. Oktober 1994 "Einsprache" an das Kreisamt Thusis. Zur Begründung führten sie unter Hinweis auf einige Artikel des Baugesetzes der Gemeinde Cazis an, eine ausreichende und den Verhältnissen angepasste Zufahrt sei nicht sichergestellt, der Bauverkehr sei für die Anwohner nicht zumutbar und es fehle ein Situationsplan mit Einzeichnung der Zufahrt. Als "Zusätzliche Bemerkung" wurde vorgebracht, für die Ausführung des Bauvorhabens würde Privatgrundbesitz befahren. Eine Kopie dieser Einsprache wurde mit Originalunterschrift versehen und eingeschrieben dem Gemeindevorstand Cazis zur Kenntnis gebracht. Der Gemeindevorstand Cazis erteilte am 20. Dezember 1994 die öffentlichrechtliche Baubewilligung; die Erledigung der privatrechtlichen Einsprache durch das Kreisamt Thusis wurde ausdrücklich vorbehalten. Diese Bewilligung wurde den Einsprechern nicht eröffnet. Im privatrechtlichen Einspracheverfahren erwog der Kreispräsident Thusis mit Verfügung vom 3. März 1995, die Einsprecher bezögen sich auf öffentliches Recht. Demgemäss verfügte er, auf die privatrechtliche Baueinsprache werde nicht eingetreten. Dagegen erhoben H.A._ und J.A._ Beschwerde an das Bezirksgericht Heinzenberg. Zur Begründung verwiesen sie darauf, dass sie keinen Bodenabtausch mit der Gemeinde getroffen hätten. C._ müsse daher, um zu seinem Baugrundstück zu gelangen, ihren Grund und Boden befahren. - In der Folge ersuchte die Gemeinde Cazis um Erteilung des Enteignungsrechts für die Verbreiterung der Strasse im Gebiet D._. Dieses wurde ihr mit rechtskräftigem Urteil des Verwaltungsgerichts des Kantons Graubünden vom 18. Juni/24. Juni 1996 erteilt. Daraufhin schrieb das Bezirksgericht Heinzenberg mit rechtskräftigem Beschluss vom 25. September 1996 das Beschwerdeverfahren der Gebrüder A._ betreffend Baueinsprache/Besitzesschutz infolge Gegenstandslosigkeit als erledigt ab. Mit gütlicher Vereinbarung vor der Enteignungskommission VII des Kantons Graubünden einigten sich die Gemeinde Cazis einerseits sowie J.A._ und die Erben des inzwischen verstorbenen H.A._ andererseits im Juli/August 1997 darauf, dass letztere der Gemeinde insgesamt 43 m2 Land für die Verbreiterung der Zufahrt in D._ abtreten. B.- Ende April 1999 begann die C._ Generalunternehmung mit den Bauarbeiten in D._. Mit Schreiben vom 26. April 1999 an die Gemeindeverwaltung Cazis und ergänzender Eingabe vom 10. Mai 1999 machten J.A._, die Erben des H.A._ sel. sowie B._ geltend, die seinerzeitige öffentlichrechtliche Einsprache vom 5. Oktober 1994 sei nicht behandelt worden. Namentlich sei die Baubewilligung den Einsprechern nicht mitgeteilt worden. Zudem sei sie verjährt. Sie rügten die Verletzung einiger baurechtlicher Bestimmungen und beantragten materiell insbesondere eine andere Erschliessung des Baugrundstücks, formell eine Zustellung des Baubewilligungsentscheids oder eventuell den Neubeginn des Baubewilligungsverfahrens. Mit Verfügung vom 26. Mai 1999 erwog der Gemeindevorstand Cazis, H.A._ und J.A._ hätten seinerzeit gegen das Bauvorhaben nur eine privatrechtliche, aber keine öffentlichrechtliche Einsprache erhoben. Nachdem das Enteignungsverfahren durchgeführt worden sei, könne auch nicht mehr von einer ungenügenden Erschliessung gesprochen werden. Das Baugesuch entspreche in allen Teilen der Baugesetzgebung. Die Baubewilligung sei am 23. September 1997 und am 22. September 1998 um je ein Jahr verlängert worden. Demgemäss beschloss der Gemeindevorstand, auf die Eingaben nicht einzutreten. C.- B._, J.A._ sowie die Erben des H.A._ sel. erhoben dagegen Rekurs an das Verwaltungsgericht des Kantons Graubünden mit dem Antrag, die Verfügung der Gemeinde Cazis vom 26. Mai 1999 aufzuheben und festzustellen, dass das Bauprojekt ohne rechtsgültige Baubewilligung ausgeführt werde; eventuell sei die Angelegenheit an die Gemeinde zurückzuweisen zur Prüfung der vorgebrachten Einwände, subeventuell zur Behandlung der Einsprache vom 5. Oktober 1994. Am 29. Juli 1999 teilte der Rechtsvertreter der Rekurrenten mit, dass die Erben des H.A._ sel. ihre Beteiligung an J.A._ verkauft hätten und dieser in deren Rechtsstellung eingetreten sei. Mit Urteil vom 16. Dezember 1999 erwog das Verwaltungsgericht, die Eingabe von H.A._ sel. und J.A._ vom 5. Oktober 1994 sei lediglich als privatrechtliche Einsprache zu betrachten. Die Gemeinde sei daher nicht verpflichtet gewesen, den Einsprechern den Baubewilligungsentscheid zuzustellen. Die Baubewilligung sei auch nicht erloschen; zwar erlösche die Baubewilligung, wenn der Bau nicht innert eines Jahres begonnen werde. Diese Frist habe jedoch infolge des in der Baubewilligung enthaltenen Vorbehalts der privatrechtlichen Einsprache erst mit deren Erledigung zu laufen begonnen, mithin mit dem Abschreibungsbeschluss des Bezirksgerichts Heinzenberg vom 25. September 1996. Seither sei die Bewilligung zweimal korrekt verlängert worden. Demnach wies das Verwaltungsgericht den Rekurs ab. D.- J.A._ und B._ haben beim Bundesgericht am 23. März 2000 mit dem Antrag staatsrechtliche Beschwerde erhoben, das Urteil des Verwaltungsgerichts aufzuheben. Sie rügen eine Verletzung von Art. 9 und 29 Abs. 1 BV. Die Gemeinde Cazis und das Verwaltungsgericht des Kantons Graubünden beantragen, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Die C._ Generalunternehmung als Beschwerdegegnerin liess sich innert Frist nicht vernehmen.