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.

Das Bundesgericht zieht in Erwägung:
1.- a) Mit dem angefochtenen Entscheid wird eine Verfügung der Gemeinde Cazis geschützt, mit welcher diese auf die Eingaben der Beschwerdeführer nicht eintrat. Tritt eine Behörde auf eine Rechtsvorkehr, zu deren Beurteilung sie zuständig ist, nicht ein, so liegt eine formelle Rechtsverweigerung vor, welche mit staatsrechtlicher Beschwerde gerügt werden kann (<ref-law> bzw. Art. 4 aBV; Art. 84 Abs. 1 lit. a OG). Die Beschwerdeführer rügen eine Verletzung des Willkürverbots (<ref-law>) und des Verbots des überspitzten Formalismus (<ref-law>). Entgegen ihrer Auffassung muss sich zwar auch unter der neuen Bundesverfassung vom 18. April 1999 die Legitimation zur Willkürrüge aus einer Norm des materiellen Rechts oder des Verfahrensrechts ergeben, welche dem Schutz der privaten Interessen des Beschwerdeführers dient (Art. 88 OG; <ref-ruling> E. 2a und E. 4 - 6). Die Berechtigung kann sich jedoch auch aus dem Verbot der formellen Rechtsverweigerung und des überspitzten Formalismus ergeben (<ref-ruling> E. 3b, mit Hinweisen).
Auf die staatsrechtliche Beschwerde ist daher einzutreten.
b) Im Verfahren der staatsrechtlichen Beschwerde wendet das Bundesgericht das Recht nicht von Amtes wegen an; es prüft nur diejenigen Rügen, die ordnungsgemäss (Art. 90 Abs. 1 lit. b OG) erhoben wurden. Die Beschwerdeführer beanstanden einzig, dass die Gemeinde und das Verwaltungsgericht in willkürlicher und tatsachenwidriger Weise die Einsprache vom 5. Oktober 1994 ausschliesslich als privatrechtliche und nicht als öffentlichrechtliche betrachtet hätten.
Nur dieser Vorwurf kann daher Gegenstand des bundesgerichtlichen Verfahrens bilden.
2.- Es ist nicht bestritten, dass das Baugesuch der C._ Generalunternehmung im September 1994 ordnungsgemäss publiziert worden war. Ein Anspruch auf Behandlung kann unter diesen Umständen nur bestehen für Einsprachen, die fristgerecht eingereicht wurden. Dies trifft auf die Beschwerdeführerin 2 nicht zu: Sie hat - wie sie selber einräumt - damals keine Einsprache erhoben. Sie konnte daher von vornherein keinen persönlichen Anspruch auf Behandlung der damaligen Eingabe durch die Gemeinde und auf Zustellung des Baubewilligungsentscheids vom 20. Dezember 1994 haben. Hinsichtlich der Beschwerdeführerin 2 ist die Beschwerde damit offensichtlich unbegründet.
3.- a) Die Beschwerdeführer bringen vor, es sei willkürlich und überspitzt formalistisch, die Einsprache vom 5. Oktober 1994 als ausschliesslich privatrechtliche zu betrachten. Willkürlich ist ein Entscheid nicht schon dann, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre, sondern erst dann, wenn er offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Willkür liegt sodann nur vor, wenn nicht bloss die Begründung eines Entscheides, sondern auch das Ergebnis unhaltbar ist (<ref-ruling> E. 2a S. 168, 124 I 247 E. 5 S. 250, 123 I 1 E. 4a S. 5, mit Hinweisen). Überspitzter Formalismus wird unter anderem angenommen, wenn eine Behörde formelle Vorschriften mit übertriebener Schärfe handhabt oder an Rechtsschriften überspannte Anforderungen stellt und damit dem Bürger den Rechtsweg in unzulässiger Weise versperrt (<ref-ruling> E. 2a S. 15, 117 Ia 126 E. 5a S. 130).
b) Es ist unbestritten, dass die Einsprache vom 5. Oktober 1994 an das Kreisamt Thusis adressiert war. Die Beschwerdeführer machen jedoch geltend, sie sei zugleich mit Originalunterschrift und eingeschrieben auch der Gemeinde zugestellt worden. Dieser Umstand kann jedenfalls für sich allein nicht zur Folge haben, dass die Gemeinde die Einsprache als öffentlichrechtliche hätte an die Hand nehmen müssen. Aus einer Eingabe muss mit genügender Klarheit hervorgehen, dass eine bestimmte Anordnung angestrebt wird (<ref-ruling> E. 5c S. 131, Urteil des Bundesgerichts vom 21. Juli 1993, in ZBl 95/1994 S. 40 E. 1b). Demzufolge muss sie grundsätzlich an diejenige Behörde gerichtet werden, die zuständig ist, die verlangte Anordnung zu treffen. Zwar hat die Rechtsprechung unter gewissen Umständen einen verfassungsrechtlichen Anspruch darauf anerkannt, dass ein bei einer unzuständigen Behörde eingereichtes Rechtsmittel an die zuständige überwiesen wird, namentlich wenn eine falsche oder zu Unrecht keine Rechtsmittelbelehrung angebracht wurde (<ref-ruling> E. 1c S. 333 f., 118 Ia 241 E. 3c S. 243 f., zit. Urteil vom 21. Juli 1993, in ZBl 95/1994 S. 40 E. 1c).
Doch folgt daraus nicht, dass auch die Kopie einer an eine zuständige Behörde adressierten Eingabe ohne weiteres als zusätzliche Rechtsvorkehr zu betrachten wäre. Dagegen sprechen insbesondere Gründe der Rechtssicherheit wie auch das Interesse des Bürgers, nicht unerwartet ein Kostenrisiko einzugehen (<ref-ruling> E. 5d S. 133).
Im vorliegenden Fall hatte die Publikation des Baugesuchs korrekt die beiden Einsprachewege an das Kreisamt und an die Gemeinde angegeben. Wenn unter diesen Umständen die Einsprache nur an das Kreisamt adressiert wurde, ist es zumindest nicht willkürlich, wenn die Behörden annahmen, es handle sich nur um eine privatrechtliche Einsprache. Zudem konnte es - auch soweit lediglich privatrechtliche Einsprache erhoben werden sollte - durchaus sinnvoll erscheinen, die Gemeinde mit einer Orientierungskopie zu bedienen. Diese wurde damit in die Lage versetzt, die öffentlichrechtliche Baubewilligung lediglich unter Vorbehalt der Erledigung der privatrechtlichen Einsprache zu erteilen, was sie denn auch getan hat. Dass auch die Kopie an die Gemeinde original unterschrieben war, ist nicht unüblich und lässt die Beurteilung der kantonalen Instanzen jedenfalls nicht als willkürlich erscheinen.
c) Es ist den Beschwerdeführern einzuräumen, dass in der Einsprache drei Artikel des Baugesetzes zitiert wurden, die angeblich verletzt worden sein sollen. Doch betrafen alle diese Punkte die Zufahrt zum Baugrundstück, also den gleichen Fragenkomplex, den der Beschwerdeführer 1 auch mit seiner eindeutig privatrechtsbezogenen Bemerkung anschnitt, für die Ausführung des Bauvorhabens würde Privatgrundbesitz in Anspruch genommen. Die Gemeinde konnte nach Treu und Glauben davon ausgehen, dass der Beschwerdeführer 1 einzig die ungenügende Zufahrt beanstandete und die Kopie deshalb der Gemeinde zustellte, weil ein allfälliger Ausbau der Zufahrtsstrasse in deren Zuständigkeit lag. Die Gemeinde hat denn in der Folge auch einen Teil der Grundstücke des Beschwerdeführers 1 enteignet und die Zufahrtsstrasse zum Baugrundstück verbreitert. Damit war derjenige Punkt erledigt, der inhaltlich einzig Gegenstand der Einsprache gebildet hatte.
d) An der Auffassung des Verwaltungsgerichts vermag auch der Umstand nichts zu ändern, dass der Kreispräsident mit seinem auch der Gemeinde zugestellten Entscheid vom 3. März 1995 zunächst festhielt, die Einsprache enthalte öffentlichrechtliche Rügen. Denn der Beschwerdeführer 1 und sein Bruder erhoben gerade gegen diesen Entscheid des Kreispräsidenten zivilrechtliche Beschwerde an das Bezirksgericht mit der Begründung, es habe noch kein Bodenabtausch stattgefunden.
Auch das spricht dafür, dass die Gemeinde willkürfrei annehmen konnte, es gehe den Einsprechern in erster Linie um eine Bereinigung der privatrechtlichen Verhältnisse.
Schliesslich ist zu berücksichtigen, dass der Beschwerdeführer 1 und die Gemeinde während mehrerer Jahre im Zusammenhang mit der Verbreiterung der Zufahrtsstrasse und dem dazu erforderlichen Enteignungsverfahren verschiedentlich miteinander in Kontakt standen. Es wäre unter diesen Umständen nach Treu und Glauben zu erwarten gewesen, dass der Beschwerdeführer 1 sich gelegentlich nach dem Schicksal seiner öffentlichrechtlichen Einsprache erkundigt hätte, wenn er die Eingabe vom 5. Oktober 1994 tatsächlich als solche verstanden haben wollte.
e) Schliesslich ist der angefochtene Entscheid auch nicht im Ergebnis unhaltbar. Gegenstand der Einsprache vom 5. Oktober 1994 war einzig die Zufahrt zum Baugrundstück. Ob diese unter öffentlich- oder unter privatrechtlichem Aspekt als ungenügend zu betrachten war, ist zwar juristisch von Bedeutung, aber vom praktischen Ergebnis her im vorliegenden Fall untergeordnet. Jedenfalls wurde die Zufahrt mit der Verbreiterung der Strasse im Bereich der Grundstücke des Beschwerdeführers 1 verbessert und damit diejenige Beanstandung behoben, die in der Einsprache vorgebracht worden war.
Dass eine andere Erschliessung des Baugrundstücks auch denkbar wäre, bedeutet noch nicht, dass die realisierte Zufahrt im Lichte des Baugesetzes ungenügend wäre. Im Verfahren vor Verwaltungsgericht rügten die Beschwerdeführer in materieller Hinsicht einerseits die Verletzung diverser baupolizeilicher Bestimmungen (Grenzabstand zur Strassenparzelle, Gebäudelänge, Anzahl Parkplätze), die aber nichts mit der Zufahrt zum Grundstück zu tun hatten, nicht Gegenstand der Einsprache vom 5. Oktober 1994 gebildet hatten und daher ohnehin nicht mehr zu prüfen waren. Andererseits brachten sie vor, die Zufahrt zum Baugrundstück sei nicht möglich, ohne privaten Boden der Beschwerdeführerin 2 zu beanspruchen.
Das hätte - soweit öffentlichrechtlich von Belang - in erster Linie die Beschwerdeführerin 2 im Einspracheverfahren vorbringen sollen, was sie damals jedoch unterliess. Die privatrechtlichen Befugnisse der Beschwerdeführerin 2 werden sodann durch die streitige Baubewilligung bzw. den angefochtenen Entscheid des Verwaltungsgerichts ohnehin nicht berührt und bilden auch nicht Gegenstand des vorliegenden Verfahrens.
4.- Die staatsrechtliche Beschwerde erweist sich daher als unbegründet. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten den Beschwerdeführern unter solidarischer Haftung aufzuerlegen (Art. 156 Abs. 1 und 7 in Verbindung mit Art. 153 und Art. 153a OG). Diese haben zudem der Gemeinde Cazis, welche als kleine Gemeinde ohne eigenen Rechtsdienst auf den Beizug eines Anwalts angewiesen war, für das bundesgerichtliche Verfahren eine Parteientschädigung zu entrichten (Art. 159 Abs. 1 und 2 OG). Der private Beschwerdegegner, der sich am Verfahren vor Bundesgericht nicht beteiligte, hat keinen Anspruch auf Entschädigung.

Demnach erkennt das Bundesgericht:
1.- Die staatsrechtliche Beschwerde wird abgewiesen.
2.- Die Gerichtsgebühr von Fr. 3'000.-- wird den Beschwerdeführern unter solidarischer Haftung auferlegt.
3.- Die Beschwerdeführer haben die Gemeinde Cazis für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.- Dieses Urteil wird den Parteien, der Gemeinde Cazis sowie dem Verwaltungsgericht, 4. Kammer, des Kantons Graubünden schriftlich mitgeteilt.
_
Lausanne, 27. Juni 2000
Im Namen der I. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: