Introduce him to lots of different puzzles. Jigsaws obviously, and tangrams (when I was little we had Multipuzzle, don't know whether you can still get that, but it's basically tangrams).
Get some simple origami sets. Oh, and paper aeroplanes. Someone gave us a box of printed papers to make into paper aeroplanes of varying complexity.
Mastermind, the game with coloured pegs - I have No Idea whether that's still around. Ooh yes, it is.
From the Bright Minds catalogue, among other places: Rush Hour is great fun, and a similar one called Tipover. They say from age 8 but I think there's a junior version too. I loved Tantrix which says it's for 6-plus (the name is because it's got knots in it, nothing dodgy
). I haven't tried the new laser mirror puzzle, though I did the online thing I think it's based on 20 years ago and found it enjoyably challenging.
As he's confident with reading, wordsearches. Crosswords if you think his vocabulary's up to it. As he gets older you can introduce cryptic crosswords - I was solving the anagram ones in my parents' crossword at the age of 11. There are puzzle books galore on the supermarket magazine racks. Junior Sudoku maybe?
Oh, teach him rhymes. Lots of verse. Allan Ahlberg, Julia Donaldson, Edward Lear, nursery rhymes, Lewis Carroll. Don't be afraid of longer poems (up the airy mountain, down the rushy glen). See if he can remember them (the shorter ones first, obviously, and don't push it).
And of course there's always chess. Can't remember when I started to learn but I was still at primary school when my 3-years-younger sister started to seriously challenge me...
Do you have access to a piano or similar? If he likes pushing buttons he might enjoy the idea of making tunes. An electronic version will do a lot of the hard work for him 