Constructions of strong and weak Lyapunov functions are presented for a feedback connection of two hybrid systems satisfying certain Lyapunov stability assumptions and a small-gain condition. The constructed strong Lyapunov functions can be used to conclude input-to-state stability (ISS) of hybrid systems with inputs and global asymptotic stability (GAS) of hybrid systems without inputs. In the absence of inputs, we also construct weak Lyapunov functions nondecreasing along solutions and develop a LaSalle-type theorem providing a set of sufficient conditions under which such functions can be used to conclude GAS. In some situations, we show how average dwell time (ADT) and reverse average dwell time (RADT) "clocks" can be used to construct Lyapunov functions that satisfy the assumptions of our main results. The utility of these results is demonstrated for the "natural" decomposition of a hybrid system as a feedback connection of its continuous and discrete dynamics, and in several design-oriented contexts: networked control systems, event-triggered control, and quantized feedback control.