Comments:

  - You commented out the "use 5.006" and then proceeded to   
    use "our".  Naughty.

  - You could get the flexibility you like in Python by
    overloading != in your signature classes, I think.
    I don't know if it would be worth it, but it might
    make you happier with Perl.

  - You have "1;" at the end of every package.  This is not
    required.  What is required is a "1;" at the end of
    every file, which you also have.

  - Why repeat the class name in the "adddependency" method?
    I think just add() might be clearer.

  - The use of mixed case in parameter names runs against
    the grain of most Perl modules ("Method" and "Files").

  - This module might be more useful if it provided 
    save() and load() methods to save dependencies to
    a file and load them again.  That way it could be
    used by compilers and other non-long-running programs
    to track up-to-dateness.  Storable should offer an
    easy solution if you like the idea.

That's all for now!

-sam