Does it have to be Compulsary?
I think too many people are concentrating on the 'compulsary' nature of Guy's suggestions, but what about non-compulsary training or licencing.
A voluntary government sponsored Internet/Security awareness course akin to the ECDL could be a useful qualification for people to have for job applications etc, and might encourage people to learn these things for themselves.
Also, at the moment Microsoft Windows (or in fact any of the other OS's) don't really include any advice on IT security, and this would be a very useful tutorial to give new PC users when they first switch the machine on.
Jonathan