Pokémon have a statistic called CP. What does it do, and why is it relevant?
Is it a substitute for the nonexistent levels and statistics, or is it something completely different?
CP is an abbreviation for Combat Power. It is an aggregate statistic that represents how powerful any specific Pokemon is, based on their IVs (Stamina, Attack, and Defense) and their current Level.
It is a safe (general) assumption that a Pokemon with a higher CP will tend to fare better in battle than one with a lower CP. If two Pokemon of the same species, CP, IV, Level, and Moveset were to battle, the fight will likely result in a draw.
CP, however, is not a determination of who wins a battle. There are a number of extra factors that influence battles:
Two Pokemon with the same CP are not always equal -- they may have different levels and IVs, making them vastly different and useful (or useless) in different cases.
CP can be increased by powering up the Pokémon through the use of Candies, and through evolution. Note, however, that CP will not cause your Pokémon to evolve -- this must be separately triggered.
Pokemon CPs can range from a minimum of 10 to an upper limit determined by their IVs and a Pokemon's Level. A list of Max CPs are available here, for those who are interested.