Propulsion by cilia is a fascinating and universal mechanism in biological organisms to generate fluid motion on the cellular level. Cilia are hair-like organelles, which are found in many different tissues and many uni- and multicellular organisms. Assembled in large fields, cilia beat neither randomly nor completely synchronously—instead they display a striking self-organization in the form of metachronal waves (MCWs). It was speculated early on that hydrodynamic interactions provide the physical mechanism for the synchronization of cilia motion. Theory and simulations of physical model systems, ranging from arrays of highly simplified actuated particles to a few cilia or cilia chains, support this hypothesis. The main questions are how the individual cilia interact with the flow field generated by their neighbors and synchronize their beats for the metachronal wave to emerge and how the properties of the metachronal wave are determined by the geometrical arrangement of the cilia, like cilia spacing and beat direction. Here, we address these issues by large-scale computer simulations of a mesoscopic model of 2D cilia arrays in a 3D fluid medium. We show that hydrodynamic interactions are indeed sufficient to explain the self-organization of MCWs and study beat patterns, stability, energy expenditure, and transport properties. We find that the MCW can increase propulsion velocity more than 3-fold and efficiency almost 10-fold—compared with cilia all beating in phase. This can be a vital advantage for ciliated organisms and may be interesting to guide biological experiments as well as the design of efficient microfluidic devices and artificial microswimmers.