This is a brief overview of brewing; there are many more recipes, which can be found on the Minecraft Wiki.
What you will need
You will only be able to start brewing after you have ventured into The Nether and killed some Blazes and collected some Blaze Rods. Many of the other ingredients you will need come from The Nether too. You should find some Nether Wart and se up a plantation near your Nether Portal so you have a steady supply.
Setting Up Your Brewing Area
Make a Brewing Stand out of a Blaze Rod and cobblestone. You will want to place it somewhere you have storage and a nearby water supply.
Optional: make a cauldron to hold water to fill your bottles. This is not necessary if you have a well nearby. A cauldron can be filled with a water bucket, and will hold sufficient water to make 3 potions.
Make some glass bottles for your potions.
The Brewing Process
Fill up three glass bottles with water, by right-clicking on either a filled cauldron or a water source block. Water Bottles will appear elsewhere in your inventory, so make sure you have three spaces available.
When you right-click on your Brewing Stand, the brewing interface will open.
Place the water-bottles in the bottom three spaces and an ingredient in the top. If the ingredient is of the right type, the brewing process will start:
When the brewing is completed (it takes 20 seconds), your water bottles will have been turned into potions! Not useful potions though.
It's time to add a second ingredient. This ingredient will determine what kind of potion you are making.
When this step has finished, you will have a useable potion.
Further brewing steps can be used to make a stronger potion, or a splash potion that can be thrown at friends or enemies.
This is an overview of how to brew some of the most useful potions. There is much more information available on the Minecraft Wiki.
Awkward potion doesn't do anything, but it is the first step to make any of the other useful potions. Awkward potion is made by using Netherwart in Step 1.
Potions of Healing
These restore health when you drink them. Use Glistering Melon in Step 2. They can be made stronger by using Glowstone in Step 3.
Potion of Regeneration
Restores health over time. Useful in tough fights against multiple foes. Use a Ghast Tear in Step 2. In step 3, you can make it last longer with Redstone, or make it more powerful using Glowstone.
Potion of Fire Resistance
Drink this and you are immune to fire. Use Magma Cream in Step 2 and use Redstone in Step 3 to make a longer-lasting version.
Potion of Strength
Makes your attacks more powerful. The ingredient for Step 2 is Blaze Powder. In step 3, you can make it last longer with Redstone, or make it more powerful using Glowstone.
Splash potions are made by adding gunpowder to a normal potion. Splash potions have a differently-shaped bottle, and can be thrown at a target.
A splash potion of healing will heal an ally (such as your pet wolf) if thrown, but more usefully will hurt undead enemies such as skeletons, zombies and zombie pigmen.
A splash potion of harming can be made by adding a fermented spider's eye to a splash potion of healing, and is extremely useful for killing large numbers of farm animals. It will also harm most hostile mobs, but will heal undead ones such as skeletons and zombies.
Recipes for some of the strange ingredients used in potion brewing.
This uses a slime-ball and blaze dust.
Make this with a slice of melon and a gold nugget (obtained by killing Zombie Pigmen or by crafting from gold bars).
Fermented Spider's Eye
This icky ingredient can be used to turn most kinds of 'good' potions into 'bad' ones with the opposite effect. The components can be arranged in any shape, so you can make this in the 2x2 grid in your inventory screen.
Here are the recipes for the most useful potions.