If you have a Pokemon like Swampert or Absol on your team and can level them enough, then you should have enough firepower to beat Tate & Liza. But if you're here, you probably don't, so...
Get the Super Rod from Mossdeep City in the house east of the Gym. Then, fish for Wailmer in Mossdeep City. They come as high as level 45, at which point they are ready to evolve and already know Water Spout and Rest.
If you add Mystic Water or Chesto Berry and perhaps Surf to the mix, you should have enough to beat Tate & Liza, whose team is weak to Water. Note that Water Spout is a spread move in Gen 3, so the calcs below only show half the damage you can do in one turn.
Lvl 46 0 SpA Mystic Water Wailord Water Spout (150 BP) vs. Lvl 42 25 HP 25 IVs / 25 SpD 25 IVs Solrock: 122-144 (99.1 - 117%) -- 93.8% chance to OHKO
Lvl 46 0 SpA Mystic Water Wailord Water Spout (150 BP) vs. Lvl 42 25 HP 25 IVs / 25 SpD 25 IVs Lunatone: 98-116 (79.6 - 94.3%) -- guaranteed 2HKO
Lvl 46 0 SpA Mystic Water Wailord Water Spout (150 BP) vs. Lvl 41 25 HP 25 IVs / 25 SpD 25 IVs Claydol: 76-90 (67.8 - 80.3%) -- guaranteed 2HKO
If you get a lower-level Wailmer, don't evolve until level 41, so you get Water Spout sooner. Take care against Solrock which can use Sunny Day + SolarBeam.
You can get Mystic Water from the Castform given to you at the Weather Institute. You can also get level 35 Sharpedo from fishing in Mossdeep City, which is immune to Psychic moves and comes with Crunch. If your Pokemon can learn the Shadow Ball TM from Mt. Pyre, that may also assist.
Otherwise, make sure your team is levelled appropriately for the battle (Tate & Liza's team is at level 41-42) and you've equipped them with boosting items for their STAB. If you're having trouble with Tate & Liza then you're going to really struggle with the Pokemon League, so maybe choose now to cull the weaker members of your team and focus on overlevelling your best Pokemon.
