My approach is to create a local CPAN mirror by using CPAN::Mini. This will be a fully functional CPAN mirror that will maybe even still fit on a CD.

If you don't want to go the route of shipping the full CPAN with your product, you can look at DrHyde's work for cpandeps ("temporary offline" unfortunately), but I guess he's got the code for tracking the dependencies online somewhere as well.