How are CPDLC VHF messages transmitted between ATC and aircraft?
For non-oceanic operations, aside from the tower radios, most ATC communications go through remote communications outlets (RCO) scattered around to get the necessary coverage.  most are co-located with VORs or other navigational aids.  The controllers are located in either a TRACON or Center facility that's often a long distance to the RCOs.  

The problem is this equipment is these systems were designed for voice comm (double-side band AM radios).  For data link, the radios operate as a radio modem using VHF data link (VDL) Mode 2.  So three things have to happen: 1. the controller needs a data link enabled workstation, 2. there has to be a network connection to the RCOs, and 3. the radios need to support VDL mode 2.  

So the real issue boils down to the two primary factors; time and money.  The implementation in the US is part of Nexgen.  To speed up the implementation, there is the alternative of leasing services of network providers such as ARINC and SITA.  

BTW, the most comprehensive reference on data link is the Global Operational  Data Link Document.