In its simplest form, intelligence is just one of many phenotypes that evolution acts on. In our case, the fittest human (originally primate) was the most intelligent, and natural selection selected those individuals.
If we wanted to do this other animals, we have a few options:
- Genetically engineer the species so that genes that confer intelligence are present and expressed.
- Perform artificial selection on the species based on intelligence.
- Change the environment around the species so that intelligence is the preferred phenotype.
Today, we do not have the technology to do #1. We actually don't know what genes (or gene combinations) confer intelligence. Also, our genetic engineering techniques are not advanced enough to work on organisms as complex as dolphins, crows, elephants, etc.
We could, and actually have, performed #2. Research with fruit flies actually led to an increased intelligence in fruit flies over a few dozen generations. However, it was discovered that this intelligence lowered the fruit flies' fitness in other areas. This may simply be a side effect of insect gene diversity, or it may point to the larger cost of intelligence.
In order for this to be successful, we would have to come up with a metric for intelligence, and then breed those animals that show higher on the metric. To avoid genetically bottlenecking the new "intelligent" subspecies, we would have to breed this species is very large numbers: hundreds if not thousands of members.
This area has the most promise: we would let nature do the work, but direct that natural process. One idea is that, in an area with otherwise limited foodstuffs, provide foodstuffs only if the species can complete certain tasks (like your puzzle example). However, this may backfire in a sense, as puzzle-solving ability of a particular puzzle is not necessarily synonymous with intelligence: just because a salmon can remember for years the exact spot in the exact stream it was born in does not mean that it is a "smart" creature in the normal sense of the word.