Pokémon Labs are the places where Pokémon Professors (Oak, Elm, Birch, Rowan, or Juniper) give the Trainer a Starter Pokémon in the beginning of the story. The Labs are the places where the Professors do their research, the research area varies between the Professor in question's area of interest.
Professor Oak is featured in Pokémon Red, Blue and their remakes, FireRed and LeafGreen. In these games, Oak either gives the Trainer a Bulbasaur, a Charmander or a Squirtle, but in Pokémon Yellow he gives the Trainer a Pikachu.
Professor Elm is featured in Pokémon Gold, Silver, Crystal and their remakes, HeartGold and SoulSilver. In these games, Elm either gives a Chikorita, a Cyndaquill or a Totodile to the Trainer. This Pokémon lab is in New Bark Town.
Each Generation has three different starter Pokémon, most of whom are Grass, Fire or Water-type Pokémon.