Frankly, I would take a set of building blocks into the classroom -- just like little children use in kindegarten.
Set one on the table, and announce that it is an object. Let a few exaggerated OOooo's and Ahhh's pass, then take another block and set next to it. - Again, announce that it is an object.
Place the second next to the first, then drop a few more onto the table. Line them all up end to end, and say: "Here is one object."
Tap the end two together, and announce that what affects one affects all of them; and push one end of the row of blocks, moving them across the table a little ways
Take two sets of three blocks and make a small pyramid; move one pyramid, then the other across the table; then push one pyramid next to the other.
Do all of this without much commentary, just the visual demonstration.
Now, announce that each block is an object, and each pyramid is an object. Looking a little amused, say that every motion can be considered a "method"; and that the number of blocks in each pyramid (maybe add 3 blocks to one pyramid for distinction)are attributes.
How far the blocks are pushed, are parameters. Ergo, the teacher him/her-self is an object with parameters, attributes, and methods -- that can use the methods within the "exposed" objects within certain parameters. (You can't push too fast or the pyramids will disconnect or fall. You can't go past the edge of the table, or you lose the objects altogether.)
Then hold up a block, and ask if anyone knows what a "string" is, letting the obvious pun stand for a moment. (This can be a seque to the "Hello World" program.)
And continue on from there.
Does one pyramid "inherit" the parameters, methods and attributes of the individual blocks?
How do the position or size of the blocks affect the stability of the pyramids?
Can you see that each pyramid or block has an interface? (the sides of the blocks or pyramids)
Are there things you can do with one block that become more difficult when dealing with the blocks in a pyramid?
The analogy goes on and on, of course, and can be expanded by shaping forms -- even some low-grade sculpture of an animal or something -- out of a large number of blocks.
(Someone in the class may decide that art is a better career choice that IT if they make a good enough sculpture. -- Hopefully, that will not be the instructor.)
A box can be used to contain a few blocks, making a simpler interface and allowing better control over all the blocks in the box -- and the other blocks can be shown to 'address' exposed parameters of the box by setting it on them.
Anyway, you asked how I would begin teaching OOP. That's about it.