Sachverhalt: A. Der Gemeinderat Menzingen erteilte Z._ am 6. Mai 2008 die Baubewilligung für die Erstellung eines Einfamilienhauses und dreier Reiheneinfamilienhäuser auf der Parzelle Nr. 316, Edlibach. Hierbei eröffnete der Gemeinderat auch die Ausnahmebewilligung der Direktion des Innern des Kantons Zug vom 24. April 2008 zur Unterschreitung des Waldabstands für das Bauvorhaben. Parallel dazu wies der Gemeinderat die Einsprachen der Nachbarn X._ und Y._ ab. Letztere fochten die Bewilligung des Bauprojekts beim Regierungsrat des Kantons Zug an. Ihre Eingaben wurden zuständigkeitshalber an das Verwaltungsgericht des Kantons Zug überwiesen. Das Verwaltungsgericht erklärte sich für die Behandlung der Beschwerden zuständig und wies sie mit Urteil vom 18. Dezember 2008 ab. B. Gegen das Urteil des Verwaltungsgerichts erheben X._ und Y._ beim Bundesgericht mit gemeinsamer Eingabe vom 13. Februar 2009 Beschwerde in öffentlich-rechtlichen Angelegenheiten. Sie beantragen im Wesentlichen die Verweigerung der Baubewilligung unter Aufhebung der ergangenen Entscheide. Z._, der Gemeinderat Menzingen und das Verwaltungsgericht ersuchen um Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Direktion des Innern spricht sich für eine Abweisung der Beschwerde aus. Das Bundesamt für Umwelt (BAFU) kommt in seiner Stellungnahme vom 24. April 2009 zum Schluss, aus seiner Sicht liege keine Verletzung der bundesrechtlichen Vorschriften über den Waldabstand vor. Die Beteiligten haben Gelegenheit erhalten, sich zur Eingabe des BAFU zu äussern. Sie haben sinngemäss an ihren Standpunkten festgehalten. 