Subclassing the module - this lets you add your own methods to the class, and replace or extend methods that are already there.
Advantage: you write very little code, and your code stays disjoint from the already-existing code.
Disadvantage: code that needs "your stuff" has to use your new subclass instead of the standard one; if you have code that already uses the old class a lot, you have to go through and change all of the class mentions from the old one to your new one.
Patching the module. There are several ways to go about this (cpan:Sub::Exporter, cpan:Class::AutoPlug, but all of them boil down to manipulating the symbol table to add your new method to the desired namespace.
Advantage: it looks like you're using bog-standard Module::X, but you get your extension.
Disadvantage: less understandable to less-experienced programmers. "But magic_method isn't there when I do perldoc Module::X!"
Extending the class by switching namespaces via package, creating the method or methods you want, and returning to your old package.
Advantage: simpler than the other two. Disadvantage: the package switch needs to occur after the package has been used, but before the method is needed.
Disadvantage: this adds a execution-order linkage between the module you're extending and the one you extend it in: the module has to be loaded, then your package statement and the sub definition have to be compiled, then after that the method's available. This might get complicated if you do a lot of patching.