Simply create a subroutine that initializes something, blesses a reference to it into the appropriate class, and returns the blessed reference. There is no enforced naming scheme (as there is in C++ or Java, for example), but many Perl hackers use new:

sub new {
    my $class = shift;                  # allow for inheritance
    $class = ref($class) || $class;   # allow indirect or
                                      # direct calling
    my $self = {};                    # create an anonymous 
                                      # array to hold member data
    bless($self, $class);             # allow for inheritance
    return $self;                     # return new object
}
[download]

That's the canonical constructor. It takes the name of the class into which to bless the object (provided automatically), discerns the proper name (whether it is called through an instance of that class or indirect means), creates an anonymous hash for member data, uses the dual-argument form of bless to be sure that the object is created as a type of the desired (not just the current) class, and provides it to the caller in a nicely wrapped package.

You will probably want to be in your own package before you declare this constructor, though.