Since your office is using primarily Windows machines, I recommend going with Samba. In general, I've found it's easier to make a Linux box use Microsoft protocols than it is to bend Windows into working with *nix based protocols (like nfs). Both do work, one works better for this situation, in my opinion.
Also, what are you trying to do? If all you need are network disk space, then you're done with just Samba. If you're looking into having a centralized authentication method as well, then you'll want Kerberos or LDAP. I've used both, but never have administered either, so someone else will have to give some advice on those.