Others are correct, overclocking won't make a tangible difference to your computer.
If you look at your Gateway manual you may find that your particular computer was actually designed to take a range of CPUs at different pricing points. Since you mention 350MHz, it's probably a Slot 1 motherboard with the CPU sitting on a little riser card. CPUs in that family were rated at 350, 400 and 450MHz. A used 450MHz CPU would be almost free now, and a very simple swap. It would give you about 25% more bang.
You need to find the maximum "clock multiplier" supported by your motherboard: this will be a setting starting at 3.0 and going to at least 4.5 in your case. Look at the biggest number: If 6.0, then 600MHz is the fastest you can go.
You can probably use Pentium III CPUs on Slot 1 cards: they're electrically compatible. You'd want a CPU that is no faster than the largest clock multiplier, and which operates at 100MHz front side bus (that's your existing memory speed). Off-hand, that would be 350, 400, 450 MHz as a Pentium II, then 450, 500, not 533, 550, some 600 MHz Pentium III. You can't use a "B" CPU: 533B, 600B. There are some none-B 600 MHz CPUs.
A little bit more RAM might also help, but there's no need to go beyond 256MB or 512MB. It may not be cost-effective: old RAM is in great demand. It will cost more than the CPU.
Well, that's way more than you probably needed to know. If it were my system and I needed it to work, I'd leave it as-is unless I came across a 350MHz PII Slot 1 part. If I didn't need it to survive the experiment, I'd pop in any Slot 1 CPU other than 533B or 600B, and see what happened for 10 seconds. Slot 1 is very robust.