Aus den Erwägungen:
2.- Der Beschwerdeführer A ist Eigentümer der Grundstücke Nrn. X und Y, GB Z. Die Beschwerdegegnerin (B AG) ist Eigentümerin der Grundstücke Nrn. S und T, GB Z. Die umstrittene Erweiterung des unterirdischen Felsenkellers liegt - grösstenteils - im Erdreich, einige Meter unterhalb des Terrains der Parzellen Nrn. X und Y. Von Bedeutung ist ferner die unstrittige Feststellung, dass der Beschwerdeführer das Baugesuch nicht mitunterzeichnet hat. Dessen ungeachtet hat die Baubewilligungsbehörde geglaubt, das Baugesuch an die Hand nehmen zu dürfen. Denn sie ging davon aus, dass dem Beschwerdeführer das rechtserhebliche Interesse am einige Meter unterhalb der Erdoberfläche liegenden Erdreich, wo der projektierte Felsenkeller realisiert werden sollte, fehle. Deshalb habe der Gemeinderat das Baugesuch ohne Zustimmung des Beschwerdeführers materiell überprüfen und bewilligen dürfen. Da es ansonsten mit den öffentlich-rechtlichen Bestimmungen im Einklang stehe, habe er (der Gemeinderat) die Baubewilligung - unter Auflagen und Bedingungen - zu Recht erteilt.
Demgegenüber vertritt der Beschwerdeführer den Standpunkt, das Interesse am strittigen Terrainuntergrund hätte ihm - dem betroffenen Grundeigentümer - nicht abgesprochen werden dürfen. Vielmehr hätte er das Baugesuch - in seiner Eigenschaft als Grundeigentümer - zwingend mitunterzeichnen müssen. Eine solche Zustimmung habe er zum Projekt indessen verwehrt, weshalb der Gemeinderat die Baubewilligung nicht hätte erteilen dürfen.
3.- a) Die Streitsache dreht sich - formell gesehen - um das Unterschriftserfordernis bei Baugesuchen. Gemäss § 188 Abs. 1 PBG in der bis Ende 2001 gültig gewesenen Fassung (fortan aPBG) war das Baugesuch u.a. auch vom Grundeigentümer zu unterzeichnen. Die seit dem 1. Januar 2002 in Kraft stehende revidierte Fassung von § 188 Abs. 2 PBG enthält dieselbe Verpflichtung. Gemäss § 188 Abs. 4 PBG in der neuen Fassung, die gegenüber § 188 Abs. 3 aPBG nicht verändert worden ist, nimmt der Grundeigentümer mit der Einreichung des Baugesuchs am Baubewilligungsverfahren teil und gibt sein Einverständnis zu Eigentumsbeschränkungen, die zur Sicherung von Auflagen verfügt werden. Nach § 192 lit. b PBG hat der Gemeinderat oder die von ihm bezeichnete Stelle zu prüfen, ob das Baugesuch mit den Beilagen den Anforderungen für eine Prüfung und Beurteilung des Bauvorhabens entspricht; ist dies nicht der Fall, verlangt der Gemeinderat oder die von ihm bezeichnete Stelle die Behebung der Mängel innert gesetzter Frist mit der Androhung, dass die Baubewilligungsbehörde andernfalls auf das Baugesuch nicht eintreten werde. Inhaltlich deckt sich diese Bestimmung mit § 192 aPBG, worin noch ausdrücklich auf die Erfordernisse gemäss §§ 188 - 190 PBG Bezug genommen worden war.
b) In seiner mehrfach bestätigten Rechtsprechung geht das Verwaltungsgericht davon aus, dass die Baubewilligung die behördliche Feststellung ist, wonach einem Bauvorhaben keine öffentlich-rechtlichen Hindernisse - insbesondere keine solchen aus dem Raumplanungs- und Baupolizeirecht - entgegenstehen (§ 195 Abs. 1 PBG; statt vieler: LGVE 1991 II Nr. 3 Erw. 2 mit Hinweisen). Diese Feststellung hängt nach der Gerichtspraxis nicht von der Person des Baugesuchstellers, sondern von den sachlichen Merkmalen des Bauvorhabens ab. Die Baubewilligung wird wohl einer bestimmten Person - dem Bauherrn - erteilt, doch richtet sie sich nur auf das Bauvorhaben in seiner konkreten Gestalt und Ausführung. In persönlicher Hinsicht ist für die Behörde wesentlich, dass ihr eine bauberechtigte Person gegenübersteht (ZBl 1985 S. 120 f. Erw. 2). Diese ist in erster Linie der Grundeigentümer, muss indessen mit diesem nicht immer identisch sein, was sich unter anderem darin ausdrückt, dass nebst dem Grundeigentümer zuweilen auch ein (weiterer) Bauherr ein Baugesuch unterzeichnen muss (vgl. dazu auch Art. 671 ff. ZGB; vgl. LGVE 1998 II Nr. 12 Erw. 4).
c) Das Erfordernis der Unterschrift des Grundeigentümers bezweckt einerseits, die Behandlung von - rein hypothetischen - Baugesuchen zu vermeiden, die mangels Zustimmung des Grundeigentümers von vornherein nicht realisierbar sind und deshalb nur nutzlosen Aufwand verursachen. Insofern hat die Bestimmung den Charakter einer Ordnungsvorschrift, welche darauf abzielt, den Baubehörden unnötige Amtshandlungen zu ersparen. Mit seiner Unterschrift manifestiert der Grundeigentümer seine Zustimmung zum Bauprojekt eines Dritten auf seinem Grundstück, womit ein ausreichendes Interesse des Baugesuchstellers an der Behandlung seines Vorhabens belegt ist (ZBl 1985 S. 120 f.; BVR 1993 S. 117; PVG 1989 Nr. 16; Mäder, Das Baubewilligungsverfahren, Zürich 1991, N 114). Die genannte Formvorschrift bietet aber nicht nur den Behörden Schutz vor Verwaltungsleerlauf. Weil der verfügungsberechtigte Grundeigentümer ganz allgemein ein schützenswertes Interesse daran hat, dass sein Eigentum nicht in unrechtmässiger Weise beeinträchtigt wird, verfolgt die Vorschrift durchaus auch den Zweck, dass die Baubewilligungsbehörde nicht wider besseres Wissen zu einem Verfahren Hand bietet, welches die Eigentumsinteressen Dritter zu verletzen geeignet ist (Leutenegger, Das formelle Baurecht der Schweiz, 1978, S. 124 f.; ZBl 1985 S. 121).
d) Der Unterzeichnung des Baugesuchs durch den Grundeigentümer kommt noch eine weitere, massgebliche Bedeutung zu. Der Gesetzgeber hat in § 188 Abs. 4 PBG an die Einreichung des Baugesuchs zwingend die öffentlich-rechtliche Rechtsfolge geknüpft, dass der Grundeigentümer damit am Baubewilligungsverfahren teilnimmt und sein Einverständnis zu Eigentumsbeschränkungen gibt, die zur Sicherung von Auflagen verfügt werden. Eine solche Einbindung in das Verfahren, verbunden mit der Verpflichtung, erforderliche Eingriffe in das Eigentum zu dulden, setzt zwingend voraus, dass sich der Grundeigentümer mit dem Bauprojekt einverstanden erklärt hat. Er bekundet dies, indem er das Baugesuch unterzeichnet. Das heisst mit anderen Worten, der Gesetzgeber hat die Gültigkeit des Baugesuchs von der ordnungsgemässen Unterzeichnung durch den Grundeigentümer abhängig gemacht. Demgemäss sieht § 192 lit. b PBG vor, dass der Gemeinderat, sollte das Baugesuch und die Beilagen den in § 188 PBG genannten Voraussetzungen nicht entsprechen, das Baubewilligungsverfahren nicht einleitet, sondern vom Gesuchsteller die Behebung der gerügten Mängel verlangt mit der Androhung, dass andernfalls auf das Baugesuch nicht eingetreten werde (vgl. Urteil B. vom 30.1.2001).
4.- Aus den wiedergegebenen Überlegungen ergibt sich, dass ein Baugesuch, welches vom betroffenen Grundeigentümer nicht mitgetragen wird, nicht bewilligt werden kann. Im vorliegenden Fall gehen die Verfahrensbeteiligten von gegensätzlichen Standpunkten aus. Während sich der Beschwerdeführer als Eigentümer des streitbetroffenen Terrainuntergrundes sieht, vertreten Beschwerdegegnerin und Vorinstanz die Auffassung, der Beschwerdeführer befinde sich in Bezug auf die strittigen Unterniveauanlagen ausserhalb seiner rechtlich relevanten Interessensphäre. Mithin tangiere ihn das strittige Bauvorhaben in seiner Eigenschaft als Grundeigentümer nicht. Folglich habe dieser das Baugesuch auch nicht mitunterzeichnen müssen.
a) Die Verfahrensbeteiligten argumentieren in der Hauptsache mit unterschiedlichen Vorstellungen über die zivilrechtlichen Verhältnisse an den streitbetroffenen Grundstücken. Auszugehen ist vom Grundsatz, dass sich Bau- und Rechtsmittelbehörden in zivilrechtlichen Vorfragen indes Zurückhaltung auferlegen und sich auf die Prüfung der Frage beschränken können, ob das Bauvorhaben in offenkundiger Weise Eigentumsrechte verletzt (LGVE 1999 II Nr. 23 Erw. 2 und ZBl 1985 S. 121; vgl. ferner: Fritzsche/Bösch, Zürcher Planungs- und Baurecht, 2. Aufl., Wädenswil 2000, S. 446, Ziff. 20.2.2.). Deshalb kann sich die Baubewilligungsbehörde auf eine kursorische Prüfung beschränken bzw. die Plausibilität des Nutzungsrechts prüfen und den Rest dem Zivilrichter überlassen. Die Abklärung eines behaupteten Rechts zur Erstellung einer Baute oder Anlage auf fremdem Grundstück kann denn auch nicht die Aufgabe der Baubewilligungsbehörde sein (im gleichen Sinne: AGVE 1987 S. 230).
b) In Bezug auf die in diesem Verfahren ausgebreitete Kontroverse sei vorab auf die im ZGB verankerte, zuweilen heikle Grenzziehung des Grundeigentums in vertikaler Richtung hingewiesen. In Bezug auf die horizontale Ausdehnung ist die problemlos zu erfassende Bodenfläche massgebend, wie sie insbesondere in Grundbuchplänen ohne weiteres festgestellt werden kann (Art. 668 Abs. 1 ZGB). Vertikal (hinsichtlich des Luftraums und des Erdreichs) erfolgt die Abgrenzung demgegenüber durch den unscharfen Ansatz des "schutzwürdigen Interesses" des Eigentümers. Art. 667 Abs. 1 ZGB legt diesbezüglich nur gerade einmal die Grundregel fest. Danach erstreckt sich das Grundeigentum nach unten soweit, als für die Ausübung des Eigentums ein Interesse besteht. Die Schranke des Grundeigentums bildet in dieser Hinsicht also konkret das Ausübungsinteresse (statt vieler: Schmid, Sachenrecht, Zürich 1997, u.a. mit Hinweis auf BGE 119 Ia 390 ff.; ferner: Meier-Hayoz, Berner Kommentar, N 2 ff. zu Art. 667; Rey, Grundriss des schweizerischen Sachenrechts, Band I, 2. Aufl., Bern 2000, Rz. 1067 ff.). Die Ausübung eines solchen Interesses soll - unter objektiven Gesichtspunkten - technisch möglich und rechtlich zulässig sein. Ein Ausübungsinteresse liegt etwa vor, wenn ein Grundeigentümer den Untergrund beherrschen und darin aus dem Eigentum fliessende Nutzungsbefugnisse ausüben kann oder wenn Vorkehren Dritter in diesem Raum die Nutzung seines Grundstückes beeinträchtigen würden. Ein allfälliges künftiges Interesse ist in die Beurteilung einzubeziehen. Diese Hinweise lassen unschwer erkennen, dass hier eine Rechtssphäre zur Diskussion steht, die sich nicht nach einem einfachen Schematismus abstecken lässt. Den Behörden kommt denn auch in Bezug auf die Klärung der Interessenlage ein erheblicher Ermessensspielraum zu, wobei auf die Umstände des Einzelfalles abzustellen ist (Weber, Das Grundeigentum im Wandel, in: Zeitschrift für Beurkundungs- und Grundbuchrecht [ZBGR] 79 S. 369).
c) Die Nutzung des Untergrundes von privaten Grundstücken steht entweder (privaten) Grundeigentümern zu oder - sofern es sich um einen Bereich im Erdreich handelt, welcher sich ausserhalb der Interessensphäre privater Grundeigentümer befindet - dem Staat (grundlegend: BGE 119 Ia 390 ff.). Der im vorinstanzlichen Verfahren beigezogene Gutachter vertrat den Standpunkt, dass dem Beschwerdeführer - bei den gegebenen geologischen Verhältnissen - bereits ab einer Tiefe von 5 bis 10 Metern unter Terrain keine rechtlich relevanten Eigentümerinteressen mehr zuzubilligen seien. Über diese Nutzung verfüge deshalb der Staat. Der Beschwerdeführer beharrt demgegenüber auf dem Standpunkt, ihm könne das Interesse am Grundeigentum nicht abgesprochen werden.
Den Akten kann nicht entnommen werden, dass der Staat im Rahmen eines Konzessionsverfahrens ein besseres Recht an der Nutzung des streitbetroffenen Untergrundes festgestellt hätte. Die dem Gericht vorliegenden Unterlagen vermitteln ein anderes Bild. Danach muss im Hinblick auf ein Baubewilligungsverfahren davon ausgegangen werden, dass der Beschwerdeführer - formell betrachtet - zunächst einmal als Eigentümer des Untergrundes von Parzellen anzusehen ist, die ihn im Grundbuch als Eigentümer auch ausweisen. Dass hier Dritte - konkret der Staat bzw. der Kanton (dazu: BGE 119 Ia 399 Erw. 5d) - ein besseres Nutzungsrecht am strittigen Untergrund der streitbetroffenen Parzellen haben könnten, ist, wie erwähnt, nicht zu sehen und kann insbesondere nach Lage der Akten keineswegs angenommen werden. Damit ist gleichermassen rechtsgenüglich dargetan, dass die Beschwerdegegnerin gegenüber den Behörden jedenfalls kein besseres Nutzungsrecht als der Beschwerdeführer am streitbetroffenen Untergrund plausibel machen kann. Mithin könnte die Baubewilligung unter fremdem Eigentum nach dem Gesagten bloss erteilt werden, wenn entweder der betroffene Grundeigentümer zugestimmt bzw. das Baugesuch mitunterzeichnet hätte oder - ausserhalb der Interessensphäre des Beschwerdeführers - der Staat der Beschwerdegegnerin eine Konzession hätte erteilen können und diese dann auch verliehen hätte. In der Tat steht dem Staat bzw. dem Kanton die Verfügungsbefugnis über den Untergrund zu, soweit sich ein in Anspruch genommener Untergrund ausserhalb der Interessensphäre eines Grundeigentümers befindet. Der Primat der Öffentlichkeit entspricht den genossenschaftlichen und föderalistischen Grundlagen der Staatsordnung. Daher ist der Staat befugt, über die Art und Weise der Nutzung des herrenlosen Untergrundes zu bestimmen. Mithin kommt ihm in dieser Hinsicht Monopolstellung zu (zum Ganzen: BGE 119 Ia 400 Erw. 5e). Dies gilt selbstredend auch in einem Kanton, in welchem hierüber keine besonderen (kantonalen) Bestimmungen erlassen wurden.
Im vorliegenden Fall muss davon ausgegangen werden, dass - mit Blick auf Aspekte der Plausibilität - nichts darauf hindeutet, dass die Beschwerdegegnerin hinsichtlich des streitbetroffenen Untergrundes Eigentümerstellung beanspruchen könnte. Ferner steht fest, dass der Beschwerdeführer dem Baugesuch nicht zugestimmt und der Kanton auch keine Konzession erteilt hat. Bei dieser Sach- und Rechtslage erweist sich die angefochtene Baubewilligung aus formellen Gründen als rechtswidrig und kann vor Verwaltungsgericht nicht bestätigt werden.
5.- Die Verwaltungsgerichtsbeschwerde ist nach dem Gesagten gutzuheissen und die angefochtene Baubewilligung aufzuheben. Die Sache ist an die Vorinstanz zurückzuweisen. Diese wird mit den kantonalen Stellen Kontakt aufzunehmen haben. Seitens des Staates (Kantons) wird alsdann zu prüfen sein, ob die Streitsache ausserhalb der Interessensphäre des Beschwerdeführers liegt. Für diesen Fall hätte der Staat erst einmal nach Massgabe der Rechtslage zu prüfen, ob er der Beschwerdegegnerin eine Konzession im Hinblick auf die Nutzung des dementsprechend herrenlosen Untergrundes erteilen könnte (vgl. dazu: Häfelin/Müller, Allgemeines Verwaltungsrecht, 4. Aufl., Zürich 2002, N 2418 ff.). Für den Fall, dass der Staat die Voraussetzungen für die Erteilung einer Konzession verneinen sollte, hätte das Bauvorhaben unter diesem Gesichtswinkel keine rechtsgenügliche Grundlage. Für den Fall, dass die in der Sache zuständige Behörde die Auffassung vertreten sollte, eine Konzession könne nicht erteilt werden, weil die Interessensphäre privater Grundeigentümer - vorab des Beschwerdeführers - dem entgegen stehe, käme die Beschwerdegegnerin, wie dargelegt, nicht darum herum, sich beim betroffenen Grundeigentümer um Zustimmung zum Bauvorhaben zu bemühen. Andernfalls wäre die Erteilung einer Baubewilligung ungültig. Mit diesen Hinweisen an die Adresse der Vorinstanz muss es sein Bewenden haben.
6.- Kostenfolgen.