This paper studies the formation and evolution of binary supermassive black holes (SMBHs) in rotating galactic nuclei, focusing on the role of stellar dynamics. We present the first N-body simulations that follow the evolution of the SMBHs from kiloparsec separations all the way to their final relativistic coalescence, and that can robustly be scaled to real galaxies. The N-body code includes post-Newtonian (PN) corrections to the binary equations of motion up to order 2.5; we show that the evolution of the massive binary is only correctly reproduced if the conservative 1PN and 2PN terms are included. The orbital eccentricities of the massive binaries in our simulations are often found to remain large until shortly before coalescence. This directly affects not only their orbital evolution rates, but has important consequences as well for the gravitational waveforms emitted during the relativistic inspiral. We estimate gravitational wave amplitudes when the frequencies fall inside the band of the (planned) Laser Interferometer Space Antennae (LISA). We find significant contributions -- well above the LISA sensitivity curve -- from the higher-order harmonics.