Some modules have an XS component which generate a DLL or .so file (depending on the OS). You will also need that if the module is of that type. On Windows it searches the current directory for the DLL, but on UNIX or Linux it uses environment variable LD_LIBRARY_PATH to find it.

Note, when placing a module in the same directory as your script, it is easy to assume this is the current directory - it might not be. @INC by default includes the current directory, not (necessarily) the directory containing your script. It will not contain your home directory unless you put the home directory in @INC yourself. You might have to code around that in a BEGIN block. See How do I get the full path to the script executing? and lib.
Update: added home directory comments