I forgot to answer the actual thread question, sorry!
DS4 started doing puzzles at 2.5, he just one day sat down and did a 50 piece dinosaur puzzle. It hadn't occured to me to show him and my older DS wasn't interested in them, so he didn't really do them much. DS4 is the puzzle kid in our family (and a boy after his puzzle-addict mother's heart, lol). He looks at the picture and finds the parts he wants to put together, like a particular dinosaur or the pirate ship, he doesn't start with the edges.
DD2 recently started being very interested in puzzles and can do a 24 piece one with some assistance, her and DS4 will sit and do every kid puzzle we own for well over an hour. I think it's about the only time they work together without someone crying! She does them the same way he does, she finds a part of the picture she's interested in doing and then works from there.
I think the big thing is finding a puzzle that they like, if they enjoy the theme, they'll be more inclined to do the puzzle. I also second the wooden jigsaw Melissa and Doug ones in the try, DD has a much easier time with those and will even do them on her own.
