High-gain free-electron lasers (FELs) are capable of generating femtosecond x-ray pulses with peak brilliances many orders of magnitude higher than at other existing x-ray sources. In order to fully exploit the opportunities offered by these femtosecond light pulses in time-resolved experiments, an unprecedented synchronization accuracy is required. In this Letter, we distributed the pulse train of a mode-locked fiber laser with femtosecond stability to different locations in the linear accelerator of the soft x-ray FEL FLASH. A novel electro-optic detection scheme was applied to measure the electron bunch arrival time with an as yet unrivaled precision of 6 fs (rms). With two beam-based feedback systems we succeeded in stabilizing both the arrival time and the electron bunch compression process within two magnetic chicanes, yielding a significant reduction of the FEL pulse energy jitter.