I think that beyond the obvious skills (encrypting everything, using HTTPS and TOR where possible) you need to instill in them a healthy sense of paranoia. If they think the government is reading their Facebook chat messages they're sure as hell not going to use it.