Here, we present a facile technique for synthesis of graphene nanosheet (GNS)-grafted double-walled carbon nanotube (DWCNT) hybrid carbon nanostructures (here after referred to as G-DWCNTs) by directly growing GNSs along the sidewalls of DWCNTs using a two-step chemical vapor deposition (CVD). DWCNTs were synthesized by floating catalyst CVD at 1300 °C using ferrocene and thiophene dissolved in ethanol. Then, GNSs were grafted onto the synthesized DWCNT bundles by thermal CVD at 1300 °C using ethanol. The sharp-edged petal-like structure of GNSs were grown along the sidewalls of DWCNT bundles while maintaining the one-dimensional structure of DWCNT. Next, DWCNTs and G-DWCNTs were dispersed in ethanol, then deposited on the paper using vacuum filtration method and used for ethanol detection. G-DWCNTs sensor exhibited a 3-fold improvement in the response to ethanol vapor compared to the DWCNTs sensor. The sensing mechanism of DWCNTs and G-DWCNTs can be described in terms of charge transfer between the gas molecules and sensing material. These results demonstrate that the facile technique by two-step CVD method provides a promising approach for simple and low-cost technique to synthesize the hybrid nanostructure of GNSs and DWCNTs. The new hybrid carbon nanostructures are attractive for gas sensing application.