I did that upgrade awhile back on a Mandrake system and found it fairly simple.
First, make sure that you have the apache-dev RPM package installed so that you have the apxs script and the appropriate header files.
Download the PHP4 sources, unpack, and run ./configure with the options appropriate for your setup (including mysql, et cetera). This step is explained in the PHP4 installation docs, which are in the tarball.
Then run make, and (as root) make install.
You then may need to go into the directory where the Apache library modules are located -- probably /usr/lib/apache -- and remove the PHP3 shared library. Edit the httpd.conf file to remove references to PHP3 (the PHP4 references should have been added by the installer, but check to make sure).
Then kill/restart httpd. You should be up and running.