When you begin the game, I personally reccommend getting Charmander. It's harder at the beginning of the game but in the long run it is helpful to have a strong Fire Pokémon. Charmander evolves into Charmeleon at level 16 and Charizard at level 36.

The very first Pokémon you should try to capture is Pikachu. Its electric-type attacks are a necessity for the battle with Misty (Gym Leader of Cerulean City). Be sure to pick up a Lightning Stone in Celadon City's Department Store to evolve Pikachu into the more powerful Raichu. You should also capture a Caterpie or Metapod, and get them evolved into Butterfree as quickly as possible. Butterfree is a good source of Psychic and various disabling attacks early in the game. Butterfree learns Confusion at level 12.

You should be sure to buy a Magikarp from the man at the Pokémon center near Mount Moon. Evolve him to level 20 as fast as you can so he will turn into Gyarados, an extremely powerful Pokémon.

The first Psychic Pokémon you should try to get is Abra. Though his Teleport is somewhat useless in battle, put him on the top of your Pokémon list and keep building his levels until he reaches level 16, when he evolves into Kadabra. Kadabra is one of the most powerful Psychic Pokémon. Try to have him learn Psybeam, Recover, and Psychic, and use a TM on him to teach him a Normal attack to round out his abilities. If you trade Kadabra to another cartridge he becomes Alakazam.

Be sure to capture Dratini by fishing with the Super Rod in the Safari Zone. He evolves into Dragonair at level 30 and Dragonite at level 55. Dragonite is the Pokémon with the highest attack power possible at level 99.

A great Pokémon to use is Lapras, who you get at the Silph Company in Saffron City. I reccommend using HM03 to teach it Surf, and use TM14 to teach Lapras Blizzard (the most powerful Ice attack). Lapras learns Ice Beam at level 38 and Hydro Pump, the most powerful water attack, at level 46.

The most essential Pokémon of all are the 3 mythical flying Pokémon. First, use Drowzee and build him up levels until he reaches level 35 at least. He will have evolved into Hypno by then. Use the TM that teaches Dream Eater to him, and make sure that he has Hypnosis. Then you'll be ready to find the 3 mythical Pokémon. First, go to the Power Plant and find Zapdos (An Electric/Flying Pokémon) and use Hypno's Hypnosis to put it to sleep, then use Dream Eater to lower its hit points to almost nothing. Be sure that Zapdos is still asleep when you throw the Pokéball, otherwise it will most likely say "You missed the Pokémon." Be absolutely certain that you use an Ultra Ball. After capturing Zapdos, replace whatever Electric-type Pokémon you have with him. Use a Rare Candy or build Zapdos up to level 51 so it learns Thunder, the most powerful Electric attack. After that, go to the cave on the way to Cinnibar Island. Here you'll find Articuno, the second mythical Pokémon. Articuno is Ice/Flying. Use the same technique with Hypno and capture Articuno. Raise Articuno to level 51 to teach it Blizzard, the most powerful Ice attack. After that, go through Cinnibar Island and clone whichever Pokémon you can from the Fossil that you have. The Helix Fossil clones Omanyte and the Dome Fossil clones Kabuto. Both are an odd pairing of Water/Rock types. Omanyte evolves into Omastar at level 40 and Kabuto evolves into Kabutops at level 40. The Old Amber which you can get from the Pokémon lab next to the museum in Pewter City will clone an Aerodactyl, a Flying/Rock Pokémon. After you have beaten Blaine from the Cinnibar Gym and Giovanni in the Viridian Gym, you will enter Victory Road, where Moltres, the last of the mythical Pokémon. Moltres, the Fire/Flying Pokémon, can be caught in the same manner as the other two birds. After that, defeat the Elite Four and Gary, and then return to Cerulean City. Withdraw your Master Ball if its in storage. Use Surf to get to a cave that is Northwest of Cerulean City and enter it. At the bottom-most level, you can capture Mewtwo, Pokémon number 150. Mewtwo was created in the Cinnibar Mansion and is "The Ultimate Pokémon." When you reach Mewtwo, immediately use the Master Ball. If you don't have the Master Ball, use the Hypno technique. It will take a long time but if you keep Mewtwo asleep it will eventually succeed. Be sure to save right before you battle Mewtwo so if something happens you can start over. Your Hypno should be at level 50 at the least if you want a sure chance of surviving.
Another good strategy is to use an Ice attack on Mewtwo such as Ice Beam or Blizzard. Mewtwo is succeptable to freeze.

My favorite team of Pokémon consists of Lapras, Moltres, Articuno, Zapdos, Dragonite, and Mewtwo. If you prefer you may switch Mewtwo with Alakazam or Hypno, but either way it will be effective. If you like, you can choose your favorite Pokémon and replace Articuno with it. I personally reccommend your strongest Ground, Grass, Fighting, or Ghost Pokémon. This will create the strongest possible team I can think of. Good luck, and remember...GOTTA CATCH 'EM ALL!

Here's a cheat to battle Pokémon from the Safari Zone with your own Pokémon and Pokéballs instead of with the Safari Game. Go to an area in the Safari Zone and walk around in it until your time runs out. Next, go to the coast of Seafoam Islands. Swim along the shoreline and eventually you will battle a creature. It will be one from the Safari Zone! The monsters you battle will always be from the last area you visit, not counting the water battles. I've used this trick to capture Pinsir, Rhyhorn, Nidoran(m), and Tauros. The areas of the shore that you can get monsters at are highlighted in yellow.

There are only 3 Moon Stones in the game that are easy to find, but 4 creatures that evolve from Moon Stones. Use a Moon Stone on Clefairy to evolve it into Clefable. Use one on Nidorino to transform it into Nidoking. Use the last one on Nidorina to turn her into Nidoqueen. Don't use a Moon Stone on Jigglypuff because you can capture a wild Wigglytuff in the Unknown Dungeon (where you catch Mewtwo).
NOTE: Nidoran(m) evolves into Nidorino at level 16, and Nidoran(f) evolves into Nidorina at level 16.
ANOTHER NOTE: I have heard from various people that there are 5 Moon Stones in the game. I myself have only found 4, 3 that you get in the game normally and one that you can find if you use the itemfinder. It is in one of the pillars in the front room of Cinnibar Mansion. I don't know where the other is.