Usually the cheapest way to get a performance boost is to stick in some extra RAM. However, this is not always that cost effective with older systems where the memory modules needed (72 pin SIMMs) are often quite expensive. As for processor upgrades - you can't generally do this without changing the motherboard too since older boards can't cope with newer faster processors. I think you may have a Intel VS440FX (Venus) motherboard - and this can only cope with processors up to 200 MHz. Change the motherboard and you need new 168 pin DIMM RAM modules. Also you'll need a new hard drive to take advantage of the Ultra DMA support on a new board's chipset.
My parents have a 200 MHz Dell system that would be around the same vintage as your Gateway machine. I'm quite well versed in stripping down desktop systems (and putting them back together) and have considered upgrading it for them. However, after careful consideration I've decided it really isn't worth it. For the money I'd need to replace the mainboard, processor, ram, hard drive - well it adds up to the cost of new system! These days you can get a good 1.3 GHz system for 500 quid (plus VAT).