Carbon nanostructures were synthesized by decomposition of different carbon sources over an alumina supported palladium catalyst via Chemical Vapor Deposition (CVD). Several experimental conditions were varied to verify their influence in the synthesis products: temperature ramping rate, pre-annealing conditions, hydrogen pre-treatment, synthesis temperature and time, together with the use of different carbon sources. Depending on the experimental conditions carbon nanotubes and nanofibers with different shapes and structural characteristics were obtained. Straight, coiled and branched morphologies are the most common. Among our findings, the addition of hydrogen plays a significant role in the structure of the carbonaceous products. For example, the decomposition of acetylene on palladium catalysts at 800 degrees C in the absence of hydrogen produces only carbon micro- spheres as synthesis products. The incorporation of increasing amounts of hydrogen modifies the outcome, from thick fibers to carbon nanotubes. To verify the level of graphitization of the synthesis products we have used high resolution transmission electron microscopy (HRTEM) in addition to Raman spectroscopy. Our results, based on these complementary techniques, indicate the decomposition of acetylene on a palladium based catalyst, produces the best degree of graphitization in carbon nanotubes for a temperature of 800 degrees C and 100 cc/min of hydrogen flow. Similar hydrogen flows on the same catalyst, produced highly graphitized nanofibers by the decomposition of methane at 850 degrees C.