Due to the increasing depths of coal mines and the low permeability of some coal seams, conventional methods of gas drainage in underground mines are facing many problems. To improve gas extraction, a new technique using water jets to drill tree-type boreholes in coal seams is proposed. A self-propelled water-jet drilling nozzle was designed to drill these boreholes. The configuration of the self-propelled nozzle was optimized by conducting drilling experiments and self-propelling force measurements. Experimental results show that the optimal self-propelled nozzle has a forward orifice axial angle at 25°, a radial angle at 90°, a center distance of 1.5 mm, and backward pointing orifices with an axial angle of 25°. The self-propelling force generated by the jets of the nozzle with 30 MPa pump pressure can reach 29.8 N, enough to pull the hose and the nozzle forward without any external forces. The nozzle can drill at speeds up to 41.5 m/h with pump pressures at 30 MPa. The radial angles of the forward orifices improve the rock breaking performance of the nozzle and, with the correct angle, the rock breaking area of the orifices overlap to produce a connecting hole. The diameter of boreholes drilled by this nozzle can reach 35.2 mm. The nozzle design can be used as the basis for designing other self-propelled nozzles. The drilling experiments demonstrate the feasibility of using the tree-type drilling technique in underground mines.