In reply to Ryan Parle:
Fix the rope at the top. If you have two ropes both of you could be cleaning two routes at the same time.
If it's a particularly dirty line with lots of stuff falling down your dead rope needs to be with you in a bag so any rocks don't fall onto it if it's dangling below you or on the ground.
Descend using a lockable device or also have something like a shunt / prussik which will lock you off while you clean a particular bit.
Clean from the top down because most of the crap will land on holds / ledges below you. These will obviously also need to be cleaned on the way down.
Loose stuff NEEDS to be got rid of. Use a crow bar or car jack if it's massive. Contrary to what JJ says - if you leave loose stuff on the route then climb a first ascent how would you feel if a complete stranger does the 2nd ascent and kills their belayer with an 8"x10" rock?
Have fun. It's hard but very satisfying work.
Wally