Some short background:
Unfortunately the Unix API doesn't provide a running program with the full path to the executable. In fact, the program executing yours can provide whatever it wants in the field that normally tells your program what it is. There are, as all the answers point out, various heuristics for finding likely candidates. But nothing short of searching the entire filesystem will always work, and even that will fail if the executable is moved or removed.
But you don't want the Perl executable, which is what's actually running, but the script it is executing. And Perl needs to know where the script is to find it. It stores this in __FILE__, while $0 is from the Unix API. This can still be a relative path, so take Mark's suggestion and canonize it with File::Spec->rel2abs( __FILE__ );