The worst interviews are ones where people come with lists of questions, and it doesn't matter what your answer was to question 1, they will then ask question 2. (There's nothing wrong with having a list of questions, for when you go blank or hit a brick wall. But they should be an aid, not the interview.) The best interviews are the ones where both of you forget that anyone's being interviewed, and you're just having a really interesting conversation with someone you didn't know half an hour ago.
It's best to tape interviews. It's not cheating. (It's very weird reading interviews done from notes or shorthand: it's like reading a reconstituted interview -- it may be what you said, but it's never how you said it).