Although the rapid neutron-capture process, or r-process, is fundamentally important for explaining the origin of approximately half of the stable nuclei with A > 60, the astrophysical site of this process has not been identified yet. Here we study r-process nucleosynthesis in material that is dynamically ejected by tidal and pressure forces during the merging of binary neutron stars (NSs) and within milliseconds afterwards. For the first time we make use of relativistic hydrodynamical simulations of such events, defining consistently the conditions that determine the nucleosynthesis, i.e., neutron enrichment, entropy, early density evolution and thus expansion timescale, and ejecta mass. We find that 10^{-3}-10^{-2} solar masses are ejected, which is enough for mergers to be the main source of heavy (A > 140) galactic r-nuclei for merger rates of some 10^{-5} per year. While asymmetric mergers eject 2-3 times more mass than symmetric ones, the exact amount depends weakly on whether the NSs have radii of ~15 km for a "stiff" nuclear equation of state (EOS) or ~12 km for a "soft" EOS. R-process nucleosynthesis during the decompression becomes largely insensitive to the detailed conditions because of efficient fission recycling, producing a composition that closely follows the solar r-abundance distribution for nuclei with mass numbers A > 140. Estimating the light curve powered by the radioactive decay heating of r-process nuclei with an approximative model, we expect high emission in the B-V-R bands for 1-2 days with potentially observable longer duration in the case of asymmetric mergers because of the larger ejecta mass.