From your description you are playing the campaign, in which case there's only one thing to do: get a Pokemon that can learn as many HM moves as possible (e.g. Cut, Surf, Fly). These moves are usually pretty mediocre at best - Surf is an exception - so you just farm it out to a so-called "HM slave". For the rest of your Pokemon you can just train whatever blows your hair. This works because the NPC trainers aren't very powerful, and there's nothing you can't beat just by getting a higher-level Pokemon. To illustrate, I once beat Misty (the Water gym leader in Pokemon R/B/Y) with Charizard. Like yeah, her water attacks are super-effective, but when her Pokemon are level 20 and my Charizard is level 36, there's no way I lose. Just about the only PvE thing where your comp matters is at the Battle Tower, but long win streaks at the Battle Tower require special tactics that is best left for another question.
Against other players, it's a completely different matter because you won't have a level advantage, and you need to build a real team. Broadly speaking there are two types of teams (this is very broadly speaking): offense and stall.
Offensive teams aim to kill the opponent before the opponent kills them. They will often have some plan that looks like this: "I'll use X to weaken my opponent's counter to Y. Once that's done, I'll bring in Y, set up, and kill my opponent's team." Their Pokemon won't be able to take many hits, if at all. If the opponent is faster with their plan, then offensive teams tend to die really quickly.
At the other end is stall. Here you have a lot of bulky Pokemon that can take hits and recover health. The basic gameplan is to absorb whatever your opponent can throw at you before winning with attrition damage (from entry hazards, Toxic, etc.). Well-built stall teams will rarely be 6-0'ed, because even if opponent gets in their stat-boosting move like Swords Dance, the stall team will be able to handle the +2 Pokemon.
A common way to build offensive teams is to figure out what Pokemon you want to sweep with. For example, say you choose Raikou. Then you figure out what Pokemon stops Raikou from sweeping. In this case special walls (e.g. Chansey) are complete halt to Raikou. Then you figure out how to stop that special wall. For example, you might play Dugtrio, which traps Chansey and finishes it off. With opponent's Raikou counter gone, you might be able to get a sweep off.
With stall teams, it's usually different. You look through the threat list of every Pokemon in the metagame, and figure out how you plan to stop them. For example say your opponent might have a Gyarados. In R/S/E, this is a Water/Flying Pokemon that usually attacks on the physical side with Ground, Flying/Rock and possibly Normal moves. It usually has Dragon Dance. But as you can see from that article, Zapdos completely crushes Gyarados. It doesn't matter if Gyarados has already used Dragon Dance, because you beat it anyway. If your team has a Zapdos, then you don't need to worry about Gyarados. You work through the threat list one by one to make sure you can account for most threats your opponent might have.
Note offensive teams also have to take the threat list into account, because otherwise you are just too fragile. But offensive teams usually rely on offensive checks, not counters. Against Gyarados for example, the plan might be to hit it hard with whatever you already have in play, such that it no longer has the health to sweep.
Ultimately building a team is not easy, and players spend hours fine-tuning. If you're doing it from scratch, Smogon (linked above) is a great resource. Pick your favorite Pokemon, then look through their analysis page to choose good partners.
