1. You just take turns playing tiles, and edges don't matter.
2. Still just playing tiles, but now edges do matter.
3. When you play a city tile, you can put a person on it, and when the city completes you get the person back.
4. Same with roads.
5. Same with monastaries.
6. Start counting points and having a winner.
7. Add farms

I've been playing stage #1 with Lily (nearly three years old) a lot lately, I've played stage #2 with a five year old, and stage #3 with a six year old. The exact rules don't matter that much, the important thing is to have fun and to teach the idea of playing a game that has rules you need to follow. For example, Lily wanted to play with the meeple as well, so we play that every time you put down a tile you also have to put a person on it.

There's also a version of Carcassone specifically aimed at kids but I think using the normal tiles with simpler rules makes more sense—why buy another game, and one that can't become more interesting as the kid gets older?

(This would work with other games as well. For example, with Dominion you could play with just money, trying to be the first to buy a Gold. Then you add in victory points, then one additional card at a time as they seem ready.)

Follow-up: Simplifying Board Games