how do I decode or create those %-encodings on the web?

    $string = "http://altavista.digital.com/cgi-bin/query?pg=q&;what=news&fmt=.&q=%2Bcgi-bin+%2Bperl.exe";
    $string =~ s/%([a-fA-F0-9]{2})/chr(hex($1))/ge;

Encoding is a bit harder, because you can't just blindly change all the non-alphanumunder character (\W) into their hex escapes. It's important that characters with special meaning like / and ? not be translated. Probably the easiest way to get this right is to avoid reinventing the wheel and just use the URI::Escape module, which is part of the libwww-perl package (LWP) available from CPAN.