OK, I just posted the liner install proceedure to another thread here, so look around for it.
As for the remaining crap - rake everything and shovel it out, if there's gravel scattered about, pick it up by hand, don't spread your fresh sand until you've pretty much picked through everything and are satisfied.
if your old sand is lumpy, tie some bigger boards to your shoes and stomp around in there crushing the lumps.