You might want to take a look at Randal Schwartz's anonymous proxy server (created for one of his WebTechniques columns).

It doesn't try to do what you're doing (replacing links to go through a CGI script), but rather uses your browser's built-in ability to use a proxy server.

Anyway, though, for what you asked about, take a look at HTML::LinkExtor (a subclass of HTML::Parser).

perldoc HTML::LinkExtor
perldoc LWP::UserAgent
[download]

You can use LWP to fetch the web page, then extract the links, then replace each link by a modified version of itself that routes the user through your program.