I'm a total noob when it comes to DNS configuration.

My client bought a domain through one company and is hosting their site with another (a virtual dedicated server). I can't find anything on the web that explains one's way through this setup.

Where do I start? Which nameservers do I use? Which company's zone files do I edit? Basically it boils down, for me that I don't understand which company takes the lead, and which piggybacks off their configuration.

Thanks in advance for the help.