How to organize private methods on Perl objects?

To my knowledge, there's no "correct" way. Perl doesn't provide the ability to hide the functions, at least that I've ever run across. What I've done is use a naming standard where I start the internal-only function names with an underscore and clearly document that they're never to be called by external callers.

EDIT: The other answers triggered a thought. In each private method, you could check the results of the "caller ()" function and abort if the caller is anyone other than the local module. Honestly, I personally wouldn't go to the trouble, but if it's really important to you for some reason, that would emphasize the private nature of these methods.

As opposed to $self->_private_sub(...)? In my mind, the $obj->_method notation is always used with function that act on an instance of your class, and other kinds of calls are always used for other kinds of functions.

But if you're going to be paranoid, why not use an unconventional way of packing your arguments that will confound anyone that tries to use your private method in an object oriented way?

sub do_stuff {
    my ( $self, %arg ) = @_;
    ...
    _private_sub( %arg, $self );
}

sub _private_sub {
    my $self = pop;
    my %args = @_;
    ...
}

All of the answers you have received so far say that it can't be done. But it can - in Perl 5.18 and later. See the section on lexical subroutines in perldoc perlsub.

Lexical Subroutines

WARNING: Lexical subroutines are still experimental. The feature may be modified or removed in future versions of Perl.

Lexical subroutines are only available under the use feature 'lexical_subs' pragma, which produces a warning unless the "experimental::lexical_subs" warnings category is disabled.

Beginning with Perl 5.18, you can declare a private subroutine with my or state. As with state variables, the state keyword is only available under use feature 'state' or use 5.010 or higher.

These subroutines are only visible within the block in which they are declared, and only after that declaration:

no warnings "experimental::lexical_subs";
use feature 'lexical_subs'; 

foo();              # calls the package/global subroutine

state sub foo {
  foo();            # also calls the package subroutine
}

foo();              # calls "state" sub
my $ref = \&foo;    # take a reference to "state" sub

my sub bar { ... }
bar();              # calls "my" sub

To use a lexical subroutine from inside the subroutine itself, you must predeclare it. The sub foo {...} subroutine definition syntax respects any previous my sub; or state sub; declaration.

my sub baz;         # predeclaration
sub baz {           # define the "my" sub
  baz();            # recursive call
}