The README for HTML::Tidy says that

You can get a distribution for libtidy at:
http://tidy.sourceforge.net/src/tidy_src.tgz

So you can either choose to follow the installation instructions detailed there, or try to find out whatever the RedHat RPM is called for libtidy.

Just as a note: That link just gets you a text file that says 'use CVS'.

Which is no help whatsoever behind my work firewall.

Note that distributions may actually split libtidy into two parts — what you need for runtime, and what you need for development. If you find a libtidy RPM package, you may also still need to search for a libtidy-dev package as well to get the headers you need to compile with.

As an aside, I had zero luck using HTML::Tidy. On my Debian system, it segfaulted as soon as I fed it a configuration option. I ended up writing my own system tidy wrappers for the project I'm currently working on (a set of ebook-related tools). Here's one of them, as an example for the curious:

#
# sub system_tidy_xhtml($infile,$outfile)
#
# Runs tidy on a XHTML file semi-safely (using a secondary file)
# Converts HTML to XHTML if necessary
#
# Arguments:
#  $htmlfile : The filename to tidy
#
# Global variables:
#   $tidycmd : the location of the tidy executable
#   $tidyconfig : the location of the config file to use
#   $tidyxhtmlerrors : the filename to use to output errors
#   $tidysafety: the safety factor to use
#
# Returns the return value from tidy
# Dies horribly if the return value is unexpected
#
# Expected return codes from tidy:
# 0 - no errors
# 1 - warnings only (leave errorfile)
# 2 - errors (leave errorfile and htmlfile)
#
sub system_tidy_xhtml
{
    my $infile;
    my $outfile;
    my @configopt = ();
    my $retval;

    ($infile,$outfile) = @_;
    die("system_tidy_xhtml called with no input file") if(!$infile);
    die("system_tidy_xhtml called with no output file") if(!$outfile);
    
    @configopt = ('-config',"$datapath/$tidyconfig")
    if(-f "$datapath/$tidyconfig");

    $retval = system($tidycmd,@configopt,
             '-q','-utf8',
             '-asxhtml',
             '--doctype','transitional',
             '-f',$tidyxhtmlerrors,
             '-o',$outfile,
             $infile);

    # Some systems may return a two-byte code, so deal with that first
    if($retval >= 256) { $retval = $retval >> 8 };
    if($retval == 0)
    {
    rename($outfile,$infile) if($tidysafety < 4);
    unlink($tidyxhtmlerrors);
    }
    elsif($retval == 1)
    {
    rename($outfile,$infile) if($tidysafety < 3);
    unlink($tidyxhtmlerrors) if($tidysafety < 2);
    }
    elsif($retval == 2)
    {
    print STDERR "WARNING: Tidy errors encountered.  Check ",$tidyxhtm
+lerrors,"\n"
        if($tidysafety > 0);
    unlink($tidyxhtmlerrors) if($tidysafety < 1);
    }
    return $retval;
}
[download]

Red Hat Enterprise Linux 4 is usually abbreviated as "RHEL 4" or "RHEL4", and not "RHL 4".

In case you weren't aware, "Red Hat Linux" already had nine major versions and was subsequently spun off as Fedora Core 1, which is now simply Fedora and is up to version 10. Red Hat Enterprise is a quite different distribution with quite different focus and support options. I very seriously doubt you're using Red Hat Linux 4, released about twelve years ago and using the Linux 2.0.x series of kernels, but that's what I read in your node.