dmckee's mention of the Chinese Room metaphor is a good one. If you or your students are interested, Jon Stoke's Inside The Machine is a fantastic book and goes into a fascinating level of depth. If you can read the first three chapters (just spend a little time at the local library, perhaps) you may get a much better idea of how to explain things. It builds up a little CPU as it describes the basics so you'll understand what comes later.
You can give them the basic "computers do math" stuff. I'd like to try to offer some suggestions on some of the bigger parts of all this. As others have mentioned, I'd suggest discussing something really simple like an 8086 or 6502. In fact, the 4004 may even be a good idea because it's so simple.
The main thing I'd try to tell them is how a CPU is basically a pipeline. Now each stage happens concurrently, but of course they didn't used to. A demonstration is probably best.
A simple CPU does one thing at a time. To execute an add it first gets the two numbers from memory, then adds them, then stores the result. The registers they use can be thought of as on CPU memory, that only stores one number at a time. You could demonstrate this by giving someone a box of cards with how to execute instructions. Someone would pass them an instruction (ADD) and two numbers (3 and 7). They would look up how to execute the instruction in the box (following the right path in the CPU), do each step, then hand the answer out.
Each instruction turns into a number. Code just turns into a list of numbers. You read a number, execute it, repeat. Showing them what assembly ends up as (i.e. the first byte is the instruction, the second and third may be data) may help with this. Where you are in the execution of the program is just the program counter, which is just another number in memory, an index into an array.
How the CPU works seems complicated, especially on modern CPUs. But it really is just a handful of very simple parts working in a predefined order. The most complex parts that exist today (like the branch predictor, cache algorithms, etc) all exist as icing to make the chip perform fast. They are totally unnecessary for the CPU to work correctly.
I took a quick look at the block diagram of the Intel 4004, you can see it on Wikipedia here. As you can see it's very simple. It's about the best you can get to break things down in a real chip. The chip's datasheet contains the list of all the opcodes and how the binary representations of the instructions are created. This occupies all of 3 pages. It's very simple for what it is. With the information in this sheet as well as a basic understanding and a diagram on the board you should be able to step through executions of things and give a basic idea.
I don't know how much binary math they know, but giving them at least an overview of adding (just base 2 math), AND, and OR should be enough to "get" it.
I hope this all helps. It took me a couple of years to really start to get it, trying to teach myself based on my already existing programming knowledge and Z80 assembly (since I was trying to program my TI-85).