So tell me, what should I do differently in my classroom from now on? What are the fundamental concepts and skills I should be teaching my students, to assist them in protecting their privacy and data?
GPG is a good thing to teach, the same as HTTPS and things like the EFF's HTTPS-Everywhere extension for most major browsers. Don't just stick to HTTPS though, make the leap to TLS/SSL and how it can be used to protect other forms of communication like e-mail.
BitTorrent Sync would be another thing I'd have a look at as it allows them to create their own Dropbox-like system, sharing files with friends etc. without entrusting their data to a third party.
Someone advised to never use free e-mail services but even with paid ones you have no guarantee your data won't be turned over. So if you want to be absolutely sure, host your stuff yourself.
Have a look at the Freedombox, https://www.freedomboxfoundation.org/, and ark-OS, http://ark-os.org/. Teach them about open source communication platforms and protocols such as XMPP (Jabber). You don't have to teach them how to set this stuff up, that would also require a working knowledge of Linux, but make them aware. Linux itself wouldn't be a bad thing to mention too.
Most importantly though, don't be an idiot. Don't share things on the internet you deem private or not for public consumption or when you do chose to do so, make sure others can't reade it.
Thats a good start anyways.
Also, I would teach them not to post or share anything on the Internet that they do not wish to come back to haunt them at a later date. Give examples of users that have had such things happen and the consequences as well (since many people do not believe it can happen to them). If they use services like Facebook, limit how much info you share (and also private info you give Facebook) and use a private browser windows while browsing such sites. Obviously this does not prevent everything, but there's no reason to make those that would watch them's jobs that much easier.
There are problems with one of your suggestions however. If I teach students how to use a VPN, I'm potentially giving them the skills to access pirated material anonymously and/or attempt to circumvent the school's safety filters. Their parents might have issue with this.
If you want to find out about a teenager's life, you'd be surprised how far talking to them will get you. Don't talk at them, don't interrogate them; just be interested without judging them. Most kids, like most grownups, are happy to trust and share secrets with anybody who understands them.
If you spied on your kids, and eg. found out they took drugs, what would you do? If you don't understand their situation, their point of view, there's nothing you could do to help them.
But if you do understand their situation, you won't need to spy on them; you'll feel it when they need your help. You'll be able to provide guidance, and since you didn't violate their trust, your kids just might accept your help.