There are 2 main ways to go. For the sake of making an example, let's say your company name is example.org :
a) Per account subdomains under your domain: All your users get a Fully Qualified Domain Name under your domain, i.e. <userid>.example.org , <nextuser>.example.org.
I would do this with a catch-all A-Record:
$ORIGIN example.org.
@ IN A 1.2.3.4
www IN CNAME example.org.
* IN A 5.6.7.8 # This one
b) "Vanity domains" going to a dedicated gateway: Say you want to offer your en users the option to set up a FQDN in their own domain, like shop.userdomain.com. In that case, I would dedicate a gateway server to handle this, and let the users create CNAME's to this gateway. Something like:
$ORIGIN example.org.
@ IN A 1.2.3.4
www IN CNAME example.org.
gateway IN A 5.6.7.8 # This one
.. and your end users must create a CNAME pointing to gateway.example.org in this example.
Notes: In both cases above I'm using A-Records, but you can also use CNAME's if that's more convenient. And your 5.6.7.8 server must look at the incoming HTTP headers and act appropriately, i.e. your programming of your webapp needs to handle the user accounts right on a per-request basis.
Best Answer
That's not going to work. A wildcard must cover a whole "domain level", you can't use it to match parts of a domain. See this and RFC 1034.