Treadmill set slowly, dog on it, treats in hand. Give generously as he walks, and for a few days, don't treat for anything else.
Treats should be very, very small, but extremely tasty. You don't want your dog to choke.
It took one session for Teddy to get with the program. A week later, she hops on and doesn't need any treats.