The #!/usr/bin/env perl uses the standard POSIX tool env to work around the "problem" that UNIX doesn't support relative paths in shebang lines (AFAIK). The env tool can be used to start a program (in this case perl) after modifying environment variables. In this case, no variables are modified and env then searches the PATH for Perl and runs it. Thus a script with that particular shebang line will work even when Perl is not installed in /usr/bin but in some other path (which must be in the PATH variable).
Then, you problem with ./script.pl not working: you said it has the executable bit(s) set, like with chmod +x script.pl ? But does it also start with a shebang (#!) line ? That is, the very first two bytes must be #! and it must be followed by a file path (to perl). That is necessary to tell the kernel with which program to run this script. If you have done so, is the path correct ? You want to try the #!/usr/bin/env perl variant ;-)