How do I fix a puncture?
Replacing a tire isn't that hard, but it will take a few times for it to seem like second-nature. If you have a road bike with skinny high-pressure tires, you can expect that the tires will be harder to remove and replace. 

This is how I do it on my touring bike, offroad bikes, cruiser, and folding bikes. You'll need a pump to match the valves used on your bike (presta or schrader), a spare tube, and a place to work. Tire levers would be quite helpful. 


Deflate the tire (if it isn't already completely flat). 
Remove the wheel from the bike. This will probably require that you disconnect the brakes (if you have rim brakes, as the vast majority of bikes do). If your bike doesn't have a quick-release hub, you'll need a wrench for this.  
Remove the tire from the wheel, if possible with the tube still inside. You may need a tire lever for this; it's a small plastic dookickey you can get in any bike store for a few bucks, usually in sets of three. You use it to pry the tube over the rim by working the edge of a tire lever under the edge of the tire and prying it over the edge of the rim, then sliding the edge of the tire around the edge of the rim; the tube should pop off when you've completed a circle. Two or three levers makes working with high-pressure tires easier. Once one edge of the tire is off, pull the whole tire and tube off the wheel in the direction of the side you were working with the tire lever, starting on the side of the tire opposite the valve. (Using a flathead screwdriver for this is not advised, as this can scratch the edge of the rim, potentially damaging the wheel. With some lower-pressure tires (such as mountain bikes or children's bikes) you may be able to remove the tire from the rim with no tools at all.) 
Search for the object that made the puncture, and remove it. This may be a thorn, or a nail, or a piece of glass, but whatever it is will likely be sharp, so be careful! You may have to feel around with your fingertips, or submerge the tube in water and look for rising bubbles, or even turn the tire inside out. If you replace the tube without finding the object that caused the flat you may well get another flat. (If no cause for the flat is presenting itself, you may be getting a flat from the rim itself or a spoke poking the tube.) 
Get your spare tube and put a little air in it, just enough to place it on the rim.  Put it on the tube, with the valve poking through the valve hole in the rim. 
Replace the tire over the tube, pinching the tire to be sure that it's not pinching the tube as you inflate the tube inside the tire. Be careful that the tire is inflating evenly; the first few times you do this, you may want to inflate it a little at a time and check as you go. 
Once the tire is inflated, re-install it on the bike, and please make sure to tighten your quick-release and hook your brakes back up. 
Get back on your bike and enjoy your (for now) shiny new tire! 


Watching a video or seeing pictures probably makes this all seem simpler; the other answers provided links to these resources. Bonus: More information that you'll ever need to know about tires and how to replace them: What Every Cyclist Should Know About Flat Tires