Logic is something that (1) everyone recognizes is valuable and (2) is obviously undertaught in most modern approaches to education; most of what people learn is fragmentary, incidental bits and pieces appended to various mathematical subjects. So I thought I would put up some very tentative thoughts on how this might be remedied. As I see it, the teaching of logic could be very roughly divided into three basic parts: pre-logic, basic early logic, and advanced early logic. In reality, though, the sorts of things one does in the 'pre-logic' stage should be done throughout, and, depending on how one decides to structure things basic and advanced early logic might overlap.
As I always tell my Intro students, logic is something we always do and, at least until you get into very, very advanced or specialized logical topics (all certainly more advanced than children are likely to get into), practically anything you learn in logic is something you already do, without realizing it, at least sometimes. Just as M. Jourdain discovered that he had always spoken in prose, so we discover that we have always thought in logic. The only thing we do when we learn logic is slow everything down, break it apart, see how it works, put it back together, as well as develop the habits to do these things -- and do them better -- on the fly.. But it helps if you already think more-or-less logically in the first place. And that is mostly just a matter of practice. So the thing you want, even before teaching children logic, is to have them do lots of logical thinking in the form of reasoning games, puzzles, and books. There are many, many options here. Looking back at what I remember of my childhood, long ago in the ancient world, there were quite a few things that were suitable in this way -- I liked Encyclopedia Brown, and Haledjian in Two Minute Mysteries by the same author, and I was enthusiastic, and I mean enthusiastic, about the game Clue, which, of course, is a reasoning game, and enjoyed Sleuth, which was a very, very simple DOS game version (I still have a copy, and occasional play it in the way people play Minesweeper). Although I rarely had the means to do scientific experiments, I also really liked books of scientific experiments -- much more, in fact, than books on scientific topics. In any case, there are many different ways to do this, and probably rigid regimentation of any sort at this level is a bad idea -- no matter what a child's interests are, it provides an occasion in some way to get started on thinking problems through logically, and this is something that really needs to be tailored to a child's interests.
Basic Early Logic
The pre-logic stage is mostly about sharpening natural skills. We actually get into the study of logic proper when we start looking at the structure of reasoning. Jumping immediately into this is probably not advisable. Rather, things at the basic early logic should share features with the things done at the pre-logic stage, only with a closer look at why the reasoning works. I suspect diagrams are generally ideal here. Two in particular seem especially worth mentioning.
(1) Venn diagrams. I think Venn diagrams are often used in rather sloppy ways, but the great advantage of them is that they are everywhere. It's easy to find logic games (such as the logic zoo) using Venn diagrams, and it's very easy to make up new versions of logic games for Venn diagrams. Most people get some Venn diagrams in their schooling, somewhere; but most people don't get much of them. I regularly have students who don't recognize them at all. They probably had them at some point, but not enough to stick. Little bits and pieces are not good when teaching or learning logic; you really need to practice and practice.
(2) Literal diagrams. Literal diagrams, on the other hand, are almost never seen; which is unfortunate, I think, because they end up being a powerful way to teach people to identify what's relevant, break apart logical arguments, and put together premises to get conclusions. And Lewis Carroll invented them to teach logic to children. (The intent is right with the author's name: when he writes for children he uses his pen name, Lewis Carroll, rather than his real name, Charles Dodgson.) The simplest presentation of how to use such diagrams is Carroll's The Game of Logic, although it's only with the Symbolic Logic that we get the full scope of what you can do with them (although, in fact, the full range of use presented in that book is simply not necessary). Literal diagrams are logically equivalent to Venn diagrams -- anything you do with one you can in theory do with the other -- but given the way literal diagrams are spatially organized they are more convenient and practical for handling anything beyond very simple problems. With literal diagrams one learns how to identify logically important information in a proposition and to use this analysis to draw conclusions, without anything getting too abstract. And since Carroll actually taught girls logic with this, it is entirely suitable for this stage. In addition, Carroll's problem sets -- hundreds and hundreds of problems, all Lewis Carroll-style -- are brilliant, as one might expect given that logic textbooks ever since have been stealing from them.
Probably around this stage, too, we should include true-false puzzles. Louis Sachar's Sidways Arithmetic from Wayside School has a handful of excellent ones, along with a number of other kinds of logic puzzle. (This is an excellent book all around, and I actually have it still on my shelf somewhere but (1) it is really more interesting as a book if children have read the Wayside School series already -- I actually started with this book, but I was weird in every way; (2) the difficulty of the puzzles varies wildly throughout the book. There's also a sequel, but I haven't read it.) But even without such books one can get the sense of what such problems are from problem 4 here. This could be linked to the literal diagrams by way of propositional versions of literal diagrams, but there are almost no resources for doing this.
Advanced Early Logic
With advanced early logic -- which I suspect would tend to begin to be suitable for children around 12ish in most cases, although this is something that I also suspect would vary considerably -- we actual get to applying formal systems, with emphasis very much on practice rather than theory. In a sense this is how Lewis Carroll arranged his logical teaching, although his own system (taught after literal diagrams), the subscript notation, is, I think, far more complicated to apply than anyone would really want. With literal diagrams students would already have been exposed to a perfectly good formal system, but it's deliberately set up to do a lot of the actual work for you -- you mostly just have to identify the logical parts of a proposition correctly, and the rules of the 'Game of Logic' completely handle the rest. In this stage we need to start making things more explicit, and this means actual logic. There are two tracks here that are important.
(1) Syllogisms. I first came into contact with syllogisms as a teenager on finding Teach Yourself Logic in the library. (Incidentally, I'm somewhat astounded to see that it was written by A. A. Luce; at the time, of course, I would not have known Luce from Adam, but Luce was in his day a pretty significant philosopher.) I loved that book, but, again, I was weird in every way. But Martin Cothran actually has a nice book for this, Traditional Logic I (he also has a DVD and answer key that goes with it, but neither of these are actually necessary); I've made use of parts of it for online logic modules for my Intro course, and any teenager could handle everything in this book without much difficulty, especially if the pace were leisurely and it were supplemented with additional practice. In any case, something like this is what I have in mind; it's very traditional -- traditional rules of syllogism, traditional mnemonics, etc. -- but I think this approach is probably the best approach at this stage. There are lots of other resources on this, although they may require digging -- almost any older 'traditional' or 'Aristotelian' logic manual will lay things out pretty well. Lots of things won't be explained, and there will be a fair amount of memorization, but at this level we're dealing with systems that are easier to use than to give rigorous explanations for.
(2) Boolean logic. If the main thing were to prepare for a philosophy course, one would get started immediately on truth tables in propositional logic and the like. But, honestly, this component of logic at this stage should be geared more toward prepping students for computer science, which will be more useful for more people. (A more computer science approach allows one easily to transition to the preferred approaches of mathematics and philosophy, whereas starting with a philosophical approach can make it hard to transition in the mathematical direction, and the mathematical approach requires much more background if one starts with it.) Truth tables should be in there, of course, but I think as a secondary matter. Really this component should be more a matter of Boolean reasoning, broadly speaking, than formal propositional logic in the sense people are taught it in philosophy departments. And that gives us where to start: basic Boolean-style algebra, the sort of thing you do with search engines. If they've had Venn diagrams, they've basically done this already -- Venn invented the diagrams as representations of algebraic logic along the lines invented by Boole. What you would be doing is making it more explicit and more algebraic, with AND, OR, and NOT as the key operators. There are lots of resources on this, too, combining Venn diagrams with explicit use of Boolean operators.
Expanding out from this, when students are comfortable with the basics of Boolean operators in a Venn diagram setting, they can easily be moved to Karnaugh maps, which should, in any case, be taught more than they are. As with literal diagrams, anything you can do with Venn diagrams you can do with Karnaugh maps, and, as with literal diagrams, Karnaugh maps are laid out for handling much more complicated problems than Venn diagrams are. Literal diagrams were designed specifically for syllogisms and Karnaugh maps were designed specifically for Boolean logic, but anything that one can do with one, one can do with the other, and anyone who has had lots of practice with literal diagrams can handle Karnaugh maps. From Karnaugh maps you can jump off in many directions but logic gates in circuits plus basic truth tables are the obvious way to go. There are quite a few resources here, too, although a lot of them go from truth tables to Karnaugh maps, whereas my suggestion here is that it should be the reverse. There's no need to rush too far or too fast here; just getting the basics of how Karnaugh maps work with respect to truth tables and logic gates is enough.
And that's it. Just getting the basics this far actually puts you (one way or another) a couple of weeks into the content of a college-level introductory logic course, whether it's taught by the mathematics department, the computer science department, or the philosophy department. And what is more, there is nothing in any of this, even at the most advanced stage, that goes beyond what any high school student with algebra under his or her belt can manage. Some of it tends to get taught already on a small scale, like the Venn diagrams. Some of it one never finds, like literal diagrams, or usually only finds at the college level, like Karnaugh maps, but it is all manageable. The main thing would just be to have lots of practice with each approach. It's actually not very much at all, and while it all requires practice, none of it is very difficult; but it's far more than students are typically taught -- even if you had for some reason to cut out literal diagrams or Karnaugh maps entirely, it would still be more than most students learn by the end of high school.