The characterization of the performance of numerical orbit propagation methods is addressed using performance curves. A systematized algorithmic approach is presented to compute the performance curves, identify the linear and non-linear regimes, and parameterize the linear zone. Also, the performance index concept is introduced, which aims to reduce the meaningful information of a performance curve (ultimately, the performance of the propagation method) into a single figure of merit. Several such performance indices are proposed.