How do I fix a leaking outside shutoff valve?
It sounds like the packing on a gate valve is failing. You can shutoff the water and attempt to repair these valves with new washers, cleaning the seat, and installing new packing material. However, the far more common approach now is to cut out the old valve and replace it with a 1/4 turn ball valve. These ball valves are much more reliable than the older gate valves, and the effort to install one is often less than the effort to repair a gate valve.

To replace the valve (assuming copper lines):


Shutoff the main
Drain the water in that pipe
Clean the outside of the pipe on either side of the valve before you make your cut (it's easier to clean first rather than after the pipe is cut)
Cut the pipe on each side of the valve
Test fit the new valve
Measure and cut a short piece of pipe to span any gap, you'll use a straight coupling between this pipe and the existing plumbing
Remove the valve, clean all ends and fittings again
Apply flux to the valve, pipes, and coupling
Connect the junction, short pipe, and valve to each other and the existing plumbing
Heat the joints with a blow torch until the flux bubbles and the opposite side melts the solder into each joint, take care not to excessively heat the valve itself
Give the pipes a few minutes to cool, you can also wipe away excess solder with a rag while it's still hot to make the result look better
Turn the water back on and check for leaks