I have a client who is interested in hosting just his online store with me, which is fine because I don't want all the traffic of their main site.

What DNS records, on my server and in the registrar, do I need to setup to have store.domain.com be hosted on my server but all other xxxxxx.domain.com to stay where they are at?

Thanks.

Just an idea, have them host everything where it is now but just set up a subdomain account as 'store.domain.com' on your machine. But on the other host, have them host the DNS entry for the subdomain 'store.domain.com' on their machine and have it point to your IP address (the one use by the web store if it is static or the shared IP address. That should do the trick.

or have them register a second domain for the store side of the business, its fairly common for companies to do that.