Existem 2 maneiras principais de ir. Para fazer um exemplo, digamos que o nome da empresa seja example.org :
a) Subdomínios por conta em seu domínio: todos os seus usuários recebem um nome de domínio totalmente qualificado em seu domínio, por exemplo, <userid>.example.org , <nextuser>.example.org .
Eu faria isso com um registro A-catch-all:
$ORIGIN example.org.
@ IN A 1.2.3.4
www IN CNAME example.org.
* IN A 5.6.7.8 # This one
b) "Domínios informais" indo para um gateway dedicado: Digamos que você queira oferecer aos seus usuários en a opção de configurar um FQDN em seu próprio domínio, como shop.userdomain.com . Nesse caso, eu dedicaria um servidor de gateway para lidar com isso e permitiria que os usuários criassem CNAMEs para esse gateway. Algo como:
$ORIGIN example.org.
@ IN A 1.2.3.4
www IN CNAME example.org.
gateway IN A 5.6.7.8 # This one
.. e seus usuários finais devem criar um CNAME apontando para gateway.example.org neste exemplo.
Notas: Em ambos os casos acima, estou usando o A-Records, mas você também pode usar o CNAME se isso for mais conveniente. E o seu servidor 5.6.7.8 deve olhar para os cabeçalhos HTTP de entrada e agir apropriadamente, ou seja, a programação da sua webapp precisa lidar com as contas de usuário por pedido.