We present results from a high-contrast adaptive optics imaging search for giant planets and brown dwarfs (>~1M_Jup_) around 122 newly identified nearby (<~40pc) young M dwarfs. Half of our targets are younger than 135Myr and 90% are younger than the Hyades (620Myr). After removing 44 close stellar binaries (implying a stellar companion fraction of >35.4%+/-4.3% within 100AU), 27 of which are new or spatially resolved for the first time, our remaining sample of 78 single M dwarfs makes this the largest imaging search for planets around young low-mass stars (0.1-0.6M_{sun}_) to date. Our H- and K-band coronagraphic observations with Keck/NIRC2 and Subaru/HiCIAO achieve typical contrasts of 12-14mag and 9-13mag at 1", respectively, which correspond to limiting planet masses of 0.5-10M_Jup_ at 5-33AU for 85% of our sample. We discovered four young brown dwarf companions: 1RXS J235133.3+312720B (32+/-6M_Jup_; L0^+2^_-1_; 120+/-20AU), GJ 3629B (64^+30^_-23_M_Jup_; M7.5+/-0.5; 6.5+/-0.5AU), 1RXS J034231.8+121622B (35+/-8M_Jup_; L0+/-1; 19.8+/-0.9AU), and 2MASS J15594729+4403595B (43+/-9M_Jup_; M8.0+/-0.5; 190+/-20AU). Over 150 candidate planets were identified; we obtained follow-up imaging for 56% of these but all are consistent with background stars. Our null detection of planets enables strong statistical constraints on the occurrence rate of long-period giant planets around single M dwarfs.