From Bulbapedia, the community-driven Pokémon encyclopedia.
Gender is a new feature released in Generation II, first for the Pokémon themselves, and then, in Pokémon Crystal, for the Pokémon trainers. This feature allowed for Pokémon breeding, as well as introduced the concept of a Pokémon egg to the series.
Gender also allowed for many Pokémon to have unofficial male and female counterparts, as demonstrated below.
Generation IV also premiered minimal differences in sprite between two Pokémon of the same species. For example, a male Pikachu will have the full tail seen in previous games, while the female is missing the very tip of it.
In Pokémon Crystal, players were given the option of choosing their trainer's gender at the start of the game. Since then, every game in the main series has had that choice.