Nailing down the brand's adjectives, as others have stated. Then, consider making moodboards of motion gleaned from cinematic sources as well as UI design stockpiles like dribbble and tumblr. (It's important to include animation examples alongside design materials. A fade in a dark theme might look cinematic or even threatening.)
Watch ads and movie credits that fit the company's adjectives for inspiration. Batman's title credits for instance might have design components that reinforce a company's image of powerful, secure, driven.
It's important to remember that sometimes what "looks good" to us won't "read right" to an audience. For instance, we associate bounciness with children and play, but too much bounce can be confusing to novice computer users. So be sure to actually put the interface in front of a child and see how they use it. Watch the user's face. Listen to the noises they make. Do they frown or grin? Or nothing at all? Sometimes, no reaction is the right reaction!
Afterwards, ask them for their impressions: "What kind of XX do you think this is?"
If you're working with a design team: ask if someone has motion design experience and can assist with creating a suite of treatments to try out.
When the company decides on a treatment, make sure it's documented with style and brand guidelines to encourage conformity.