How do non-native speakers get to perceive tones in Chinese?
Here are some different things that I have seen that has helped people pick up tones:

Starting out


Most books use graphs which show how each of the tones rise, fall, flatten etc (example here). It helps some people to see the difference visually and the graphs show how great an extent the tones differ.
The tones also have names (not official) e.g. rising, falling. Show the learner the graphs and ask them how they would describe each of the tones. Then ask them to pronounce tone X based on their descriptor.
Almost everyone I've seen starting with tones have started with the exercise: mā, má, mǎ, mà.
This is a bad habit, but it helps some people: using your head or your hand to move in the right direction of the tone while saying it. May help with beginners, but not recommended to keep this habit for long.


Stepping up


Try using pairs of words, I suggest using names of places because the speaker will have something they are familiar with e.g. běijīng， táiwān， shànghǎi
Counting 1 to 10 is a good exercise because it covers all four tones and as per above the speaker is familiar with the concept so they can concentrate on learning.
Family members is another good one (bàba, māmā) that uses a variety of tones.


Becoming competent


A good exercise for learning tones is practicing basic songs. I prefer to use children's songs than pop music as people tend to get distracted by the meaning of pop songs rather than concentrating on learning.
Learn to recite simple poems (again, don't concentrate on meaning, just on exercising your tongue and mouth)
There is a concept which has spread across children's Mandarin classes in the West. I will check with my wife what it is called. It involves getting children to read and recite very old writing where the meaning is completely obscured. The purpose as with the examples above is to make the learner concentrate more on how they are speaking and getting the tones precise than understanding what they are saying.
Practice reading out loud, even to yourself, as often as possible. This helps to train the mouth. Once you become more fluent start singing along to your favourite pop songs.


In my personal experience learning tones is one of the hardest skills and it took me at least 5 years before I started getting over 90% correct in conversation. My 5 year old son, who had the benefit of learning as a baby from his mother and grandparents, still corrects me daily when I slip up.