Right.
First if you can upgrade to php 4.3.1 then this would be much easier as gd support is built in.
I'll go for png and jpeg libraries as well
However
1) Install the zlib library, required for png library
http://www.gzip.org/zlib/
2) Then get the png libraries and install
http://www.libpng.org/pub/png/libpng.html
(installation of all these libraries is pretty easy and can normally be done simply with
./configure
make
make test
make install
however check the install and readme files first)
3) Install the jpeg libraries
ftp://ftp.uu.net/graphics/jpeg/
You need th jpegsrc.v6b.tar.gz
(If I rememeber correctly you need to copy a makefile from a subdirectory to it's main directory for this to work, it's detailed in the readme though)
4) Install GD
http://www.boutell.com/gd/
Then you need to reconfigure php. There is a great how-to on how to do this under plesk in the how-to forum but add in --with-gd --with-jpeg-dir=[DIR] --with-png-dir=[DIR]
Sorry for not going through the exact lines and config details but I already have them installed and so can't backtrack.