Windows Server provides a certificate authority service. However, it's not clear from its documentation how (or if) the root certificate gets distributed to clients.
The method used for distribution depends on the type of CA you setup (standalone/enterprise).
For a standalone or non-microsoft CA you generally distribute this with a group policy.
When you install an Enterprise certificate authority in a domain, this happens automatically.
When you install an enterprise root CA, it uses Group Policy to propagate its certificate to the Trusted Root Certification Authorities certificate store for all users and computers in the domain.
It's my experience that once you setup the CA and the Cert is stored in ADDS, a computer will grab it on next boot and store in the computer trusted root store. I generally put CA's in all AD domains I manage as it opens up options for using CA for all your certificate needs with out any additional work for domain member computers. This includes the Windows Server 2008 R2 SSTP VPN or L2TP IPSec which uses certificates. Traditional PPTP does not use certificates.
Slightly unrelated, but if you want people to VPN in during login, you should use GPO to push a VPN config or when you manually create the VPN on a computer check the "make available for all users" box which stores the VPN config in the public profile rather then the specific users profile. Once that's done, before login, click the switch user button (vista/7) and you'll see a new VPN icon bottom right by the shutdown button. That solves the problem of "a new user logging in without being on the network first".
Lastly, when you create the root CA, be sure it's running Windows Enterprise or the Certificate Service will be crippled (in Standard ed.) and I wouldn't make the expiration less then 10 years to save you some work in the future.
A standard practice is to distribute any Trusted Root certificates, including within your own domain, via Group Policy Objects (GPO). This can be done by creating a new GPO with proper linking and Security Filtering against the Domain Computers and Domain Controllers BUILTIN Security Groups. This ensures that domain joined Windows computer object's have a standardized set of Trusted Root certificates.
The GPO itself can be found in
Computer Configuration\Policies\Windows Settings\Security Settings\Public Key Policies\Trusted Root Certification Authorities and designating the correct store. Clients will then receive the policy upon restart and/or during their next GPO processing interval, which can be forced using the
gpupdate /force command.