This is indeed the classic question an question of considerable depth, and I applaude you for meerly asking, instead of assuming.
1. I agree with a couple of the other answers in that 500 MHZ is still adequate to run most applications well. At this time no upgrade is really necessary for processor
2. I also agree that you should upgrade your memory. Any IT professional will tell you that big memory equals big performance. In fact, get as much as you can afford, and that will extend the life of you computer considerably. I recomend 256 MB or more if your Notebook will take it.
3. Finally, if you want to improve the performance of your computer, consider a operating system upgrade. I recomend upgrading to Windows 2000. It is rock solid and improves performance exponentally. There a few program that do not run well on Windows 2000, so I recomend creating a partition on your hard drive, and installing a Dual Boot of Windows 98 and Windows 2000.
If you can wait for it, I recomend looking at purchasing Windows XP when it comes out in October, as it will run almost all applications that will not run in 98, but contains performance improvements of 2000. You can download trial for $10 from Microsoft website. Try that and see if you like the results.
4. One more thing... some suggested a HD upgrade... if you can find a faster HD to put in your Notebook, it also can improve speed considerably, but RAM first