You can pay whoever you registered your domain with (godaddy for example) to host your domains. I think some registrars might even do it for free. I managed a data center for 5 years and we always hosted a customer's domains for them. I am not sure what other hosting providers do but I would think some will host your domains and some will charge you to do so.
The alternative is to setup a name server such as bind and point your NS records at your own name server. It is not hard to setup a name server. If you need any help just let me know.