Where does this phrase comes from?
According to Bulbapedia, this phrase is a rough translation from the Japanese games :
The Japanese equivalent is Get Pokémon! (Japanese: ポケモンゲットだぜー！ Pokémon get da ze~!, also spelt ポケモンＧＥＴだぜー！)
When did the phrase Gotta catch 'em all first appeared?
While the previous answers are correct, it is important to notice that this phrase first appeared on both anime and game.
You can see on the North America's and European's version of the Gameboy game Pokemon Red and Pokemon Blue the same phrase :
But which one of the anime or the game came first?
As @DavePhD mentionned in the comments, Gotta catch 'em all is a registered trademark. One of its first registration on June 23, 1998 mentions
entertainment services, namely, arranging and conducting competitions in the field of playing video games; stage presentations; video game presentations relating to video games; production, presentation, distribution, and syndication of animation, motion picture films, and television programs; and production and presentation of video tapes
which includes both the anime and the game. So we can say that Gotta catch 'em all appeared with the general airing of Pokemon in the United States.
Note that the first episode was broadcasted before the game was released in the United States : the TV Show was aired on September 8, 1998 while the game was first sold on September 28, 19981.
1 Wikipedia links : the first episode and the games