Edit: 2 problems with this: 1) use My::Module; breaks things when the package is actually implemented in same file, so comment that out. 2) wrong order ot bless. The correct is bless $self, $class;, I use bless $self => $class; to be reminded of the correct order.

package My::Module;
sub new {
    my ( $class, $param_hr ) = @_;
    $param_hr = {} unless defined $param_hr;
    my $self = { # hashref or arrayref
        key            => 0,
        format         => 0,
        #...
    };
    bless $self => $class; # now your hash is an object of class $clas
+s.
    if( exists $param_hr->{'key'} ){ $self->key($param_hr->{'key'}) }
    else { warn "param 'key' is required."; return undef }
    return $self; # return the hash, sorry now blessed into a class in
+stance, hallelujah
}
# get or set the key
sub key {
  my $self = $_[0];
  my $akey = $_[1]; # optional key
  print "you called key() method on object '$self'\n";
  if( defined $akey ){
    print "key() : changing key to '$akey'\n";
    $self->{'key'} = $akey;
  }
  return $self->{'key'};
}
1;
package main;
# uncomment only if My::Module is in separate file:
#use My::Module;

# the notation module->new adds "module" as the first argument to the 
+new() params.
# so here is how $class is set in your question, although YOU dont pas
+s class, Perl does.
my $mod = My::Module->new({
'key' => 123,
});
die unless defined $mod;
# the same notation applies when calling the method
# Perl passes the object ref ($self=$mod) to the method as a first par
+am
print "my key: ".$mod->key()."\n";
[download]

Sometimes defining constants via Readonly or otherwise is useful

Thx, bliako, this is definitely the tree I want to bark up. I have nearly syntactic perl now, but I think I'm missing the forest for the trees here:

$ ./1.MY.translate.pl
Can't locate My/Module.pm in @INC (you may need to install the My::Mod
+ule module) (@INC contains: /home/bob/perl5/lib/perl5/x86_64-linux-gn
+u-thread-multi /home/bob/perl5/lib/perl5 /etc/perl /usr/local/lib/x86
+_64-linux-gnu/perl/5.26.1 /usr/local/share/perl/5.26.1 /usr/lib/x86_6
+4-linux-gnu/perl5/5.26 /usr/share/perl5 /usr/lib/x86_64-linux-gnu/per
+l/5.26 /usr/share/perl/5.26 /usr/local/lib/site_perl /usr/lib/x86_64-
+linux-gnu/perl-base) at ./1.MY.translate.pl line 23.
BEGIN failed--compilation aborted at ./1.MY.translate.pl line 23.
$ cat 1.MY.translate.pl
#!/usr/bin/perl -w
use 5.011;

package My::Module;

sub new {
  my ( $class, $param_hr ) = @_;
  $param_hr = {} unless defined $param_hr;
  my $self = {    # hashref or arrayref
    key    => 0,
    format => 0,

  };
  bless $class, $self;    # now your hash is an object of class $class
+.
  if ( exists $param_hr->{'key'} ) { $self->key( $param_hr->{'key'} ) 
+}
  else { warn "param 'key' is required."; return undef }
  return $self; # return the hash, now blessed into a class instance, 
+hallelujah
}

1;

package main;
use My::Module;

# the notation module->new adds "module" as the first argument to the 
+new() params.
# so here is how $class is set in your question, although YOU dont pas
+s class, Perl does.
my $mod = My::Module->new(
  {
    'key' => 123,
  }
);
die unless defined $mod;

# the same notation applies when calling the method
# Perl passes the object ref ($self=$mod) to the method as a first par
+am
print "my key: " . $mod->key() . "\n";

$
[download]

Why does perl want to look elsewhere for package MY::Module ?

Oops, if you implement a package on same file, you don't use it. I have edited out use My::Module; and also fixed a couple of typos. And also the most important part: it should be bless $self, $class . This always makes me remember the order bless $self => $class; I have edited the original post.