The primary difference between PHP 3 and PHP 4 was that the previous release executed each line of code as it read it in the script, whereas the newer release converted the entire thing to a special internal representation of the code before executing it. The difference is crucial! In PHP 3, each line needed to be read as PHP script, converted into something that can be executed, then executed. If that same line was reached again (eg it was part of a function or inside a loop), it would be read from the script file again, converted into something that could be executed, and executed. As you can see, there was lots of repeated donkey work involved!
In PHP 4, the script is only read once, and converted to an internal representation of it. This results in much faster execution of scripts, particular where repeated code is found. This same paradigm is found in both PHP 4 and 5, and it has the interesting side effect that you can - with the right software - save the compiled version of the PHP script for later use. That is, PHP reads your script, converts it to the internal representation, then saves that representation. Then, when the script is called again, the pre-saved representation is used rather than the original script. This turns out to save a vast amount of processing power, and the best part is that because the PHP is saved before it is executed, pages cached in this way don't lose any of their "dynamicity" - they can still connect to databases and show user-specific content.
Although there are a selection of accelerators for PHP, few would argue that the real leader in the field is Zend's own product, Zend Performance Suite. For a while, there was a worthwhile free competitor in ionCube's PHP Accelerator, but a lack of updates (and lack of the technological innovations that Zend introduced) has left it behind. ZPS is a powerful (if somewhat expensive) way to make your PHP script performance rocket.
The best part about PHP code caches such as ZPS is that they automatically check for changes in the original PHP script, so that if you make an edit to the source code, it recaches it automatically. This means that from both a user and developer point of view, ZPS is essentially transparent: you can't notice it's there, apart from the speed up.
The interesting thing about ZPS is that the performance improvement it brings is usually at least 2x, rising up to about 8x for particularly complex scripts, and maybe more depending on your circumstances. This is huge, particularly when you consider that the price starts at $1875 (at the time of writing), which is much, much lower than buying at least one new server to get the same kind of performance boost.
If you want a speed boost but don't necessarily need the best, you can also try APC or Turck MMCache. However - and this is quite a big proviso - do not expect these two products to work well with your PHP version. At the time of writing, only ZPS is known to work flawlessly with all releases of PHP.