The answer is quite specific to where you're signing up. There's no intrinsic connection between domains, subdomains, and hosting accounts -- you could have example.com hosted somewhere, and subdomain.example.com hosted somewhere totally different if you wanted. It's all about your host, their setup, and how you/they set up DNS.
You could accomplish this somewhat easily by having two sites, one for example.com and one for *.example.com, and have the latter base the document root on the first part of the name. In Apache, this is as simple as
VirtualDocumentRoot /path/to/site/subdomains/%1
As far as a browser would be concerned, each name represents a different site, and there'd be little or no leakage between sites if cookies are set up properly. The only problem would be FTP access, if you decide to grant that -- each user would have to be set up to have their subdir as their home dir, and ideally chrooted or something so they couldn't go and look at other people's stuff. Obviously, that will require some cooperation with/from your web host. (At the very least, in order to use VirtualDocumentRoot
, they'd need to have mod_vhost_alias running. There are other ways involving mod_rewrite, but any way you do it is going to have the same issue with FTP access.)