With a Freewheel and Derailleur

1. Move the shifter one or more positions in the desired direction. Keep pedalling.

Approximate time required: about two seconds max.

With a Fixed Gear

(But what is a fixed gear?)

1. Buy new sprocket. This might require counting the teeth of the existing one if you've forgotten.
2. Stop. Get off the bike. Get your tools.
   
3. Remove rear wheel. Notice the chain kept in place hooked over the derailleur appendix.
   
4. Unscrew sprocket. The loose bit of dangly chain is looped over the gear so that gravity keeps it in place as you heave. The red lever in both the pics is being pushed down.
   
5. Continue to try to unscrew sprocket.
   
   
6. Grunt a lot and finally manage to unscrew sprocket. Thick leather gloves highly recommended.
   
7. Apply bandages to where you grazed your knuckles on the spokes unscrewing sprocket.
8. Clean and lube hub thread and new sprocket thoroughly.
   
9. Screw on new sprocket.
10. Clean, oil, and store old sprocket.
11. Replace wheel and chain.
12. Go for a ride.
13. Make a conscious effort to crank hard and take in a couple of hills to bed the new kit in.
14. Hope very much you didn't pick a tooth count that really is too hard.

Approximate time required: about 20 minutes after the third or fourth go.

:-)