I have a directory "Math" containing several files "EM.pm", "Levy.pm", "Log2.pm", and so on. Should I place my library dirs in a subdir "Site" so that I have to "use Site::SomeDir::SomeLib" for each library, to avoid namespace conflicts?

Yes, as you've discovered, avoiding namespace conflicts is crucial. Math was unfortunate because it clashed with a heavily used CPAN top level namespace. You need to choose a top level namespace for all your non-CPAN works that is unlikely to clash with a CPAN or core Perl module. I'd look for a name that is short, descriptive of your organisation, and easy to search for. "Site" is a bit too generic for me - searching CPAN for "Site" just now returned 2457 results, while "Barrabas" returned just one (an obscure module written by one Rajstennaj Barrabas :).

What are the best practices for storing locally generated libraries?

Perl provides a lot of flexibility, there are many good ways to do it. Some excellent free and general advice can be found at Modern Perl:

You may choose never to release any of your code as public CPAN distributions, but you can use CPAN tools and conventions to manage even private code. The Perl community has built amazing infrastructure. Take advantage of it.

For more detail on this amazing infrastructure and some specific tools, see Modern Perl's "CPAN Tools for Managing Distributions" sub-section.

It's important to distinguish between a module and a distribution - again see Modern Perl for details, especially the "Designing Distributions" sub-section. Note that a distribution contains a unique name and single version number (often taken from its primary module). Instead of lumping all your modules into a single monolithic distribution, consider breaking them into a set of (highly cohesive, loosely coupled) distributions, all under the same top level namespace. Your comprehensive set of "Math" modules, for example, looks like a natural choice for a distribution.

The most important aspect of any module is not how it implements the facilities it provides, but the way in which it provides those facilities in the first place.

-- Damian Conway in Ten Essential Development Practices

Oh, and don't forget about the importance of getting your interfaces right. A couple of related Perl Monks nodes I wrote a while ago:

• On Interfaces and APIs (discusses the dark art of Interface Design)
• Writing Solid CPAN Modules