The earliest stage of star formation is the assembly of giant molecular clouds (GMCs) from the diffuse interstellar medium (ISM). Although the Milky Way allows us to study cloud and star formation in exquisite detail, nearby galaxies provide valuable laboratories to study the influence of galactic structure, interstellar conditions and large-scale physical processes on the properties of GMCs and their evolution. I present new results from the PdBI Arcsecond Whirlpool Survey (PAWS, PI: E. Schinnerer), which has mapped the CO emission in M51 at ~40 pc resolution and is sensitive to GMCs with masses above ~10^5 solar masses. Unlike the CO emission in nearby dwarf galaxies, which mostly arises in discrete clouds, much of the CO emission in M51 resides in bright kpc-sized structures that bear little resemblance to local GMCs. By comparing the GMC populations of M51 to those of M33 and the Large Magellanic Cloud, we find clear evidence for environmental effects on GMC properties: clouds in M51 have higher mass surface densities and larger velocity dispersions relative to GMCs of comparable size and mass in the nearby low-mass galaxies. The slope of the molecular mass distribution in the arm and interarm regions of M51 differ by ~0.4 dex, suggesting different cloud formation and dispersal mechanisms operate in these environments. On cloud scales, we find strong variations between the star formation rate and molecular gas surface densities within M51's disk; gas kinematics appear to be crucial for understanding these variations.