We study cosmological perturbations in a brane-world scenario where the matter fields live on a four-dimensional brane and gravity propagates in the five-dimensional bulk. We present the equations of motion in an arbitrary gauge for metric perturbations in the bulk and matter perturbations on the brane. Gauge-invariant perturbations are then constructed corresponding to perturbations in longitudinal and Gaussian normal gauges. Longitudinal gauge metric perturbations may be directly derived from three master variables (separately describing scalar, vector and tensor metric perturbations) which obey five-dimensional wave-equations. Gaussian normal gauge perturbations are directly related to the induced metric perturbations on the brane with the additional bulk degrees of freedom interpreted as an effective Weyl energy-momentum tensor on the brane. We construct gauge-invariant perturbations describing the effective density, momentum and pressures of this Weyl fluid at the brane and throughout the bulk. We show that there exist gauge-invariant curvature perturbations on the brane and in the bulk that are conserved on large-scales when three-dimensional spatial gradients are negligible.