I would make them methods. Reasons for this:
Treat them like other code. There is no reason not to. In a class, letting the routines be methods rather than functions (or whatever you want to call it) are the idiomatic norm, not the exception.
Consistency is good on a more pragmatic level too. By having all routines being methods, you don't need to keep track of whether $self / $class should be shifted off @_ or not. You don't need to worry about which routines are called in a particular way -- they're all $self->whatever(). I find myself making this specific mistake surprisingly often when some things were made subroutines.
The problem with not passing around $self (i.e. treating them like methods) is that sooner or later you'll need it in a routine in order to call a method on $self, and then you'll need to rewrite all of the things that call this routine, and everything that calls those routines, etc.
If a routine is clearly not related to the object instance ($self), make it a class method (shift off $class, call the method like this: My::Class->whatever() ) instead, because...
You almost certainly will want to override one of them in sub classes sooner or later, for the same reason you might want to override the rest of your methods. If you write a CPAN library, this is even more frustrating for other people who have needs to tweak the code that you didn't anticipate at the time.