Hey! I was about to post the same algorithm (written slightly differently), found in perlfaq5: "How do I select a random line from a file?" You can find the proof by induction here, by guess who. Mine looked like this:

my ($i, $jokekey);
++$i && rand($i) < 1 && ($jokekey = $_) for (keys %hash);
[download]

Less readable than your sub, but same idea.

However, I wouldn't use it this way in production. Like you said, it always iterates through all the keys of the hash before it returns the random key. The benefit you gain by not needing to know how many elements isn't really a benefit. The following snippet will give you the same benefit and it's easier to read, and (probably) more efficient:

sub choose {
  #assumes 1st param is \%knockknocks
  my $jokeref = shift;
  my @setups = keys %$jokeref;
  return $setups[rand @setups];
}
[download]

Now if the jokes are kept in a separate file, that could change everything ;-)