How do I set up wildcard subdomains?

I need to allow multiple members to point to my site by setting a subdomain in their DNS to point to my IP. Within my site, I look at the request's full host name (e.g.: sub.domain.com) and apply a unique template for each registered member, or return a "Server not Found" for non-members. This allows pages to display using their page theme and their domain within the URL.

In the past, using my own internal server, I could just set the default Apache web site to handle this, or set a site using a different IP.

There are too many members to consider building and updating a list of aliases. Also, it looks very awkward to try this through cpanel.

I have a vps server, and can get a second IP. The other option I see is getting full root access and making modifications to the system. I would prefer not to do this, as I am pleased with the current support.