The New York Times says that while so-called brain exercises (like Sudoku or computer applications claiming to work out your brain) can improve your skills at those very specific tasks, they're not terribly effective overall. So what is a successful form of brain exercise? Apparently, physical exercise.
In humans, exercise improves what scientists call "executive function," the set of abilities that allows you to select behaviour that's appropriate to the situation, inhibit inappropriate behaviour and focus on the job at hand in spite of distractions. Executive function includes basic functions like processing speed, response speed, and working memory, the type used to remember a house number while walking from the car to a party.