Normally, in freezing weather, this is caused by water freezing (and being helped in its task by grime, e.g. salt and dirt and stuff).
My procedure for this is generally:
1) Bring the bike inside or somewhere warm so that any ice/water can melt/evaporate off the bike. The evaporation is key -- if you just let it melt and then re-freeze, its going to cause more of a headache. I normally bring the bike in for the night when I want to deal with this.
2) Remove the brakes, thoroughly clean the bosses and brakes with rubbing alcohol and regrease and reinstall them. The brakes should move freely on the bosses. I find that this helps, but I find that cleaning the bosses and replacing the V-brake itself is sometimes a better option -- its not very expensive, and sometimes the crud works itself into places that you won't be able to clean out.
3) Make sure the cables are in good condition. If your cables are old/grimy/worn, you may need to replace them. Some people suggest lubing the brake cables, but this is against many manufacturer recommendations -- ymmv, if you choose to lubricate them.
4) Adjust the V-brakes the usual way. Not really specific to the problem, but you may as well do it at this point.
Fenders may help with preventing grime to get in, but they're a bit of a hindrance if ride in snow since it gives somewhere to pack...
As for greases/lubes, note that their viscosity and properties change with temperature, so you may want to take that into consideration (e.g. regular old white lithium grease vs a low temperature one).
And there's a good chance you'll be dealing with this multiple times in a given winter.
If its not cold, steps 2,3,4 are still good ones to follow for troubleshooting sticky V-brakes.