Term::Gnuplot is not a requirement for installing Math::Pari. Look:

E:\new\Math-Pari-2.010500>perl -MTerm::Gnuplot -e 1
Can't locate Term/Gnuplot.pm in @INC (@INC contains: C:/Perl/lib C:/Pe
+rl/site/lib .).
BEGIN failed--compilation aborted.

E:\new\Math-Pari-2.010500>perl Makefile.PL
Setting up Math::Pari with Perl 5.006001 on MSWin32 version 4.0;
   cc=cl, gccversion=, ccflags='-nologo -O1 -MD -DNDEBUG -DWIN32 -D_CO
+NSOLE -DNO_STRICT -DHAVE_DES_FCRYPT  -DPERL_IMPLICIT_CONTEXT -DPERL_I
+M
PLICIT_SYS -DPERL_MSVCRT_READFIX',
   ld=link, ldflags='-nologo -nodefaultlib -release  -libpath:"C:/Perl
+\lib\CORE"  -machine:x86', optimize='-O1 -MD -DNDEBUG'.
Found GP/PARI build directory in ./pari-2.1.5
     (integer-formatted version 2001005).
...Generating libPARI/paricfg.h ...
Scanning header files...
Note (probably harmless): Errors reading from pipe: '', exit=512: cl -
+nologo -E -DWIN32 utils/inc.h 2>&1
Creating libPARI/paricfg.h...
Problems with numeric interface codes noted:
  May be harmless: non-unique string interfaces for numeric interfaces
+:
    29 meaning "GGp GG GGD0,L,p"
      (appears for agm, besseljh, bnrconductorofchar, ellheightmatrix,
+ ellordinate, ellpointtoz, ellztopoint, idealprimedec, ideleprincipal
+,
 incgamc, qfbprimeform, rnfconductor, rnfinit, rnfpolred, theta)
  Possible problems with Math::Pari interface to GP/PARI:
        unexpected value of string interfaces for numeric interfaces:
    29 meaning "GGp GG GGD0,L,p" (was meaning "GGp" in 2.1.3)
      (may affect functions idealprimedec, rnfconductor)
Checking if your kit is complete...
Looks good
Note (probably harmless): No library found for -lm
...Processor of family `ix86' detected
...I will use assembler build of type 'ix86'.
...Assembler is GNU assembler
Note (probably harmless): No library found for -lm
Writing Makefile for Math::PARI::libPARI
Writing Makefile for Math::Pari
[download]

So just skip it.
As for being walked through a successfull install, visit Tutorials, check out Writing, Installing, and Using Perl Modules, and do it by hand. If you get stuck, come back (CPAN is great when it works, so is CPANPLUS, but if it's not working, do it by hand, it's how most people install modules, especially when they're having trouble).

My target machine is a Linux Mandrake 9.1 box. It's got a default Perl that is 5.8.

Are you aware of the Locale issue? (read links this).

MJD says "you can't just make shit up and expect the computer to know what you mean, retardo!"

I run a Win32 PPM repository for perl 5.6.x and 5.8.x -- I take requests (README).

** The third rule of perl club is a statement of fact: pod is sexy.