Steve Blank has already covered this in depth in his book 4 Steps to the Epiphany, as well as a video here: http://startupweekend.wistia.com/medias/tao3s8hf7l

My approach is based on his outline, with a twist.
1) I try and conduct the interviews at the customers office or place of work, at minimum on their devide (computer, mobile phone) so I can ask to see how they work.
2) I never try and sell them on a the solution, but work hard to truly understand if/where the problem is.
3) Always provide guidance to the conversation, but ask open ended questions.
4) Ask questions like "What do you do 3 minutes before, and after, you do that action (or use our product)?

Other tips would be
- Write down the words they use. Metaphors and taxonomies are VERY important to ensuring your product is approachable.
- Use 3 simple slides: Problem, Current Solutions, Proposed Solution

Hope that helps.