What did the Buddha teach about magic and fortune telling?

The Buddha considered such practices as fortune telling, wearing magic charms for protection, fixing lucky sites for building, prophesizing and fixing lucky days to be useless superstitions and he expressly forbids his disciples to practice such things. He calls all these things 'low arts.'

"Whereas some religious men, while living of food provided by the faithful make their living by such low arts, such wrong means of livelihood as palmistry, divining by signs, interpreting dreams... bringing good or bad luck... invoking the goodness of luck... picking the lucky site for a building, the monk Gotama refrains from such low arts, such wrong means of livelihood."

D.I, 9-12

Then why do people sometimes practice such things and believe in them?

Because of greed, fear and ignorance. As soon as people understand the Buddha's teachings, they realize that a pure heart can protect them much better than bits of paper, bits of metal and a few chanted words and they no longer rely on such things. In the teachings of the Buddha, it is honesty, kindness, understanding, patience, forgiveness, generosity, loyalty and other good qualities that truly protect you and give you true prosperity.

But some lucky charms do work, don't they?

I know a person who makes a living selling lucky charms. He claims that his charms can give good luck, prosperity and he guarantees that you will be able to pick three numbers. But if what he says is true then why isn't he himself a multi-millionaire? If his lucky charms really work, then why doesn't he win the lottery week after week? The only luck he has is that there are people silly enough to buy his magic charms.

Then is there such a thing as luck?

The dictionary defines luck as 'believing that whatever happens, either good or bad, to a person in the course of events is due to chance, fate or fortune.' The Buddha denied this belief completely. Everything that happens has a specific cause or causes and there must be some relationships between the cause and the effect. Becoming sick, for example, has specific causes. One must come into contact with germs and one's body must be weak enough for the germs to establish themselves. There is a definite relationship between the cause (germs and a weakened body) and the effect (sickness) because we know that germs attack the organisms and give rise to sickness. But no relationship can be found wearing a piece of paper with words written on it and being rich or passing examinations. Buddhism teaches that whatever happens does so because of a cause or causes and not due to luck, chance or fate. People who are interested in luck are always trying to get something - usually more money and wealth. The Buddha teaches us that it is far more important to develop our hearts and minds. He says:

Being deeply learned and skilled. Being well-trained and using well-spoken words; this is the best good luck. To support mother and father, to cherish wife and child and to have a simple livelihood; this is the best good luck. Being generous, just, helping one's relatives and being blameless in one's actions; this is the best good luck. To refrain from evil and from strong drink, and to be always steadfast in virtue; this is the best good luck. Reverence, humility, contentment, gratitude and hearing the good Dhamma; this is the best good luck.
Sn. 261-265