Well, I always think there are two phases to requirements gathering. There's the business requirements- the things the business requires the software/site to accomplish (this should come from the business owners and BAs), and then there's user requirements. It's the user requirements that you gather from researching the users. Interviews will give you these requirements, so long as you make an effort to listen for what the user needs and not just what they want. After all, a person might want steak for dinner...but it might be off their diet!
Once there are business requirements and user requirements, the two should be reconciled and compared to technical requirements to determine what is actually technologically feasible.
As for how to process interview data, I am a huge fan of affinity diagramming (which you can read about here). It's also an excellent chance to bring people in to demonstrate how important user needs in. If you can get a BA or someone in to work on it with you, they can start to see for themselves how important these needs are.
As far as documentation goes, well... there's any number of ways. I prefer light documentation, myself. Ideally the affinity diagram would be it's own documentation. But that doesn't work if you need to communicate it to other stakeholders. Still, keep it short- bullet points of what and why are good. In my experience even though people say they want 'reports' they rarely read them if they're lengthy. Or they skim them and miss the important stuff.