That is a question best answered by an entertainment lawyer. Cost and difficulty depends on who you have to clear the sample with. Start by contacting the publishing agency. I'd go through a lawyer though.
Accually I probably wouldn't clear the sample. Tried once on a 70's jazz hit. Got approval from the artist and the publishing agency. But they wanted 20,000$ up front(which wasn't unreasonable). That was 80% of the projects total budget so it didn't happen.
Unless you got serious doe to clear the samples, + more serious doe to push the project I wouldn't bother clearing it. Just use it, if you make money, they'll holla at you(you will end up paying a lot more though if you clear it after the fact). Like I said though, talk to a lawyer.
