I think you should put the package declaration on the first non comment line of the file, and before any use statements. Two reasons:

Firstly if you use a modlue that exports symbols into the caller's namespace, then those symbols will only visable in the package that used the module. eg:

package foo;

use File::Copy;

# Code here.

package bar;

# Won't work, as File::Copy was not used in this package.
copy('source','dest');
[download]

If you put the use line before the package line, then you are importing into the default package (main), if you then change packages then your imports will not be visable.

I don't know if the situation is different with pragmas such as strict, but I would say it is a poor habit to get into.

Secondly, in the Perl 6 specification it says in Synopsis 10: Packages that:

As a special exception, if a braceless package declaration occurs as the first executable statement in a file, then it's taken to mean that the rest of the file is Perl 5 code.

In other words, If you write your perl 5 packages and classes so that the package statement comes first, the they are less likey to break when run by a perl 6 aware interpreter.