The realization of many promising technological applications of graphene and graphene-based nanostructures depends on the availability of reliable, scalable, high-yield and low-cost synthesis methods. Plasma enhanced chemical vapor deposition (PECVD) has been a versatile technique for synthesizing many carbon-based materials, because PECVD provides a rich chemical environment, including a mixture of radicals, molecules and ions from hydrocarbon precursors, which enables graphene growth on a variety of material surfaces at lower temperatures and faster growth than typical thermal chemical vapor deposition. Here we review recent advances in the PECVD techniques for synthesis of various graphene and graphene-based nanostructures, including horizontal growth of monolayer and multilayer graphene sheets, vertical growth of graphene nanostructures such as graphene nanostripes with large aspect ratios, direct and selective deposition of monolayer and multi-layer graphene on nanostructured substrates, and growth of multi-wall carbon nanotubes. By properly controlling the gas environment of the plasma, it is found that no active heating is necessary for the PECVD growth processes, and that high-yield growth can take place in a single step on a variety of surfaces, including metallic, semiconducting and insulating materials. Phenomenological understanding of the growth mechanisms are described. Finally, challenges and promising outlook for further development in the PECVD techniques for graphene-based applications are discussed.