As well as learning all the theory of computer science, it can also be worthwhile teaching children a brief overview of how it has developed over time - i.e. to know about some of the most significant people involved in creating new technologies and to know about some of the most important and famous computers from the past.
View facts and videos about the history of computing on BBC iWonder.
Two creative way of doing this are to challenge the children to research about the history of computing themselves and then either present their findings as a timeline or use their findings to help solve the clues of a crossword puzzle (e.g. generated using http://www.puzzle-maker.com/crossword_Entry.cgi):