Native design files, 150ppi at size minimum, all links and fonts packaged (or outlined). Unless they're working in Quark, then it should be .PDF using the X-4 standard--we don't support Quark (die already!).
This is going to vary from shop to shop depending on the software suite being used--many shops still only have Flexi or Coreldraw and require .EPS for everything.