We report the discovery of a planetary-mass companion, HD 106906 b, with the new Magellan Adaptive Optics (MagAO) + Clio2 system. The companion is detected with Clio2 in three bands: $J$, $K_S$, and $L^\prime$, and lies at a projected separation of 7.1'' (650 AU). It is confirmed to be comoving with its $13±2$ Myr-old F5 host using Hubble Space Telescope/Advanced Camera for Surveys astrometry over a time baseline of 8.3 yr. DUSTY and COND evolutionary models predict the companion's luminosity corresponds to a mass of $11±2 M_{Jup}$, making it one of the most widely separated planetary-mass companions known. We classify its Magellan/Folded-Port InfraRed Echellette $J/H/K$ spectrum as L$2.5±1$; the triangular $H$-band morphology suggests an intermediate surface gravity. HD 106906 A, a pre-main-sequence Lower Centaurus Crux member, was initially targeted because it hosts a massive debris disk detected via infrared excess emission in unresolved Spitzer imaging and spectroscopy. The disk emission is best fit by a single component at 95 K, corresponding to an inner edge of 15-20 AU and an outer edge of up to 120 AU. If the companion is on an eccentric ($e>0.65$) orbit, it could be interacting with the outer edge of the disk. Close-in, planet-like formation followed by scattering to the current location would likely disrupt the disk and is disfavored. Furthermore, we find no additional companions, though we could detect similar-mass objects at projected separations $>35$ AU. In situ formation in a binary-star-like process is more probable, although the companion-to-primary mass ratio, at $