Although it took some searching, this nugget was quite simple.
One of my clients has a Linux Certificate Authority and none of the Windows systems would give an invalid or unknown certificate authority error when visiting a company website that used a cert created by the CA.
Get your root certificate ready, then fire up the Group Policy Management Console (or gpmc.msc). Either create a new group policy or use the Default Domain Policy to deploy it to every system.
Right-click the policy of your chosing and select Edit... go to Computer Configuration > (Policies, if you are using Windows 2008 ) > Windows Settings > Security Settings > Public Key Policies > Trusted Root Certification Authorities, right-click and choose Import... and using the import wizard browse over to your root certificate and you are done.
Within a few days most computers on the domain should have the certificate, aside from the stragglers who never seem to be on the network.