In Visio (I have 2007) you go to the VB editor (Alt-F11), and then to the Object Browser (F2). Under classes you can see that the Shape objects have a Hyperlinks property. Again under classes you can see that the Hyperlinks objects have an Add method. I can't write some code to demonstrate this now, but this procedure should get you there with a little experimentation...

UPDATE: Done some experiments myself. If $shape refers to some shape in the current document, then the following code creates a hyperlink, that turns up in the context menu of the shape.

my $link = $shape->AddHyperlink();
$link->{Description} = "Google";
$link->{Address} = "http://www.google.de";
[download]

This is a problem with Visio and not with Perl. You will then have to read the Visio documentation and find out what the appropriate method is.