Just damp enough to hydrate/fluff-up the algae(the green stuff mostly isn't lichen) is best. It'll then brush off pretty cleanly. If it's fully wet it'll tend to smear around unless you have a load of extra water with you to rinse down the rock and brush between scrubs.
Fiend's comment about not overbrushing damp grit is true on soft bits, less so on hard bits. If it's mostly scrittle I.e. loose grit you're trying to clear then you're better cleaning it when it's dry. If it's uncleanably scrittly/soft and is likely to erode with use then you might consider stabilising, but that's a whole different topic.