I don't have anything to add to the technical that Jun and Rentaroo mentioned but I'll throw out a couple of things I've done. I believe that once a person can backroll (even just sitting down) I take them on Erik's journey through everything Erik can think of that falls that way. I like to get people away from thinking as fast as I can. Thinking during ukemi is not a good thing in my opinion--before and after but not during.
I've also been known to set up obstacle courses once they can fully roll forward and backwards. Obstacles include people, moving jo, backward rolls into forward rolls, elevated jo (on pylons or whatever), knee walking around pylons into forward rolls, 2 jo on the ground as a distance obstacle, etc.
A couple of times I've put people in a circle and had the person in the middle throw ukes at those outside the circle with a randori grab. The idea is to wake people up to the idea that something going on over there might not stay there. This one scares me though and I would choose my participants very carefully (definitely not beginners) as people tend to be asleep sometimes and I'd rather wake them up while keeping them in one piece. It's the idea but...
It's interesting how we each have it differently. I find it harder to get people to forward roll and that backward rolls come really easy.