When and how is CPDLC established?
Using CPDLC makes life easier for pilots so we typically use it whenever it is available and logon shortly after takeoff.

When departing Frankfurt there is no rush as CPDLC is not available until crossing into Maastricht Radar. Continental USA does not have it so you lose CPDLC after Moncton Center. 

ATC will often remind you, or ask you to logon if you have forgot as it makes life easier for them too. Where VHF is available we usually use a combination of voice and CPDLC. 

Over the ocean, out of VHF range, we have to establish HF radio contact with Shanwick or Gander radio and do a Selcal check to insure we have a backup communication method.