みなさんレスありがとうございます。
なるほど…最初のリンクを生成する時点で%を%25にエンコードしておく必要があるんですね。

>じゃなきゃ表示時にもう一回urlエンコードすりゃいいだけの話

>http://www.example.com/hoge.cgi?a=xxx&b=yyy
>みたいなものもありうるとするならば、渡す前の方で適切にエンコードしておかないとだめですな。

urlパラメータに入るURLは、一般的なURLか前述したような文字コードを含んだURLが大半を占めるのですが、
ユーザー投稿式なので、何が来るかわからないという点を考えると、
最初のリンク生成の時点で適切なURLエンコードをしておいた方がいいようですね。

教えていただいた事を踏まえて、最初のリンク生成時に%を%25にエンコードする様スクリプトを組んだ所上手く動きました。
皆さんありがとうございます。
しかし、この方法だとhoge.cgi?a=xxx&b=yyyのようなものが来た時にダメとの事なので、
もう少し適切に処理させたいと思うのですが、またまた上手くいきません。
というか、どういう風に処理したらいいか分からないという感じです。

$elem =~ s/(https?:\/\/[\w\.\~\-\/\?\&\+\=\:\@\%\;\#\%\$]*)/<a href=\"$script?url=$1\">LINKはこちら<\/a>/go;
$elem =~ s/\%/\%25/go;

1行目は日本語混じりの文章($elem)の中にURLが張られた場合、それを「LINKはこちら」というリンクに置換させています。
そして、2行目で%→%25にしているわけですが、これだと当然問題が。

・本文中の文章の中にURL以外の%があっても置換してしまう。
・&などが来るとダメ？

「%だけじゃなくてちゃんと全部エンコードすればいいじゃないか」　とは思うのですが、
本文中から(https?:\/\/[\w\.\~\-\/\?\&\+\=\:\@\%\;\#\%\$]*)にマッチする文字列だけをエンコードさせる方法がわかりません。
どのようにしたらいいでしょうか？
本文中にはURLが複数箇所張られる可能性も考慮したいです。
度々の質問失礼しますが、ご教授の程よろしくお願いします。