You have to teach them both the general concepts ("data lives in things called files, each file lives in a folder, folders are arranged in a hierarchical tree-like structure") - but you also have to teach them to actually use these things, and you have to wait for each student to have done The Task that is being asked of them. Because if you just talk in vague abstractions, it's not going to sink in as much as Doing The Task will.
If you have any sort of opportunity to observe a elementary or middle school computer class, I strongly urge you to. It's very enlightening.
(Actually, observing any kind of class is very interesting. I used to do it at least once a year for work. I know that every profession is probably super interesting to an outside observer, but - especially as a parent - that was wildly interesting and worthwhile.)
You take the same approach with programs (web browsers as opposed to simply Chrome, spreadsheets as opposed to simply Excel, etc.).
Once they have the common ground, you can expand on differences, but always OS- and program-neutral, because schools shouldn't be a marketing tool.
The idea is that students should be able to use any computer in a very basic extent. It doesn't take much.
> (Though, how do you choose which distro to use for Linux? Or do you just make them walk uphill each way on the command line?)
You pick the one that has the most common ground with the other OSes.