We present HST optical transmission spectra of the transiting hot Jupiter WASP-12b, taken with the STIS instrument. From the transmission spectra, we are able to decisively rule out prominent absorption by TiO in the exoplanet's atmosphere. Strong pressure-broadened Na and K absorption signatures are also excluded, as are significant metal-hydride features. We compare our combined broadband spectrum to a wide variety of existing aerosol-free atmospheric models, though none are satisfactory fits. However, we do find that the full transmission spectrum can be described by models which include significant opacity from aerosols: including Rayleigh scattering, Mie scattering, tholin haze, and settling dust profiles. The transmission spectrum follows an effective extinction cross section with a power-law of index alpha, with the slope of the transmission spectrum constraining the quantity alphaT = -3528+/-660 K, where T is the atmospheric temperature. Rayleigh scattering (alpha=-4) is among the best fitting models, though requires low terminator temperatures near 900 K. Sub-micron size aerosol particles can provide equally good fits to the entire transmission spectrum for a wide range of temperatures, and we explore corundum as a plausible dust aerosol. The presence of atmospheric aerosols also helps to explain the modestly bright albedo implied by Spitzer observations, as well as the near black body nature of the emission spectrum. Ti-bearing condensates on the cooler night-side is the most natural explanation for the overall lack of TiO signatures in WASP-12b, indicating the day/night cold-trap is an important effect for very hot Jupiters. These finding indicate that aerosols can play a significant atmospheric role for the entire wide range of hot-Jupiter atmospheres, potentially affecting their overall spectrum and energy balance.(abridged)