Gauge is a measure of the number of stitches in your knitted fabric per 10cm (4") of width, and how many rows there are in a 10cm length.
To knit an accurate gauge swatch, you need to cast on enough stitches to make a square at least 10cm wide, plus enough either side to make a non-rolling border. The border makes your swatch much easier to work with.
To work out how many stitches to cast on, find the gauge stated in your pattern, add on 6 stitches to ensure that the area that you measure isn't distorted by the edge, and add another 4 stitches for the border.
Example swatch
Say we have a worsted weight yarn, with a stated gauge of 20 stitches per 10cm over stockinette stitch on 4.5mm (US size 7) needles. Cast on 20+6+4 = 30 stitches.
Starting with the suggested needle size, work two rows in garter stitch (ie knit both rows).
Stockinette section with garter stitch border:
Row 1: Knit
Row 2: Knit 2, Purl to last 2 stitches, K2
Repeat Rows 1 and 2 until your knitting is roughly square.
Work 2 rows in garter stitch.
Bind off (cast off) your stitches.
Wet-block your swatch
I recommend wet-blocking all your swatches before checking gauge, as when knitting gets wet it often changes size, and most knitting will be washed eventually. Working from a wet-blocked swatch reduces the chance of any unpleasant gauge surprises.
Thoroughly soak the swatch in tepid water, using a little detergent if you want to.
Once it's soaked through (you may need to leave it in the water for a few minutes) squeeze as much water out as you can without twisting, to avoid distorting the swatch or damaging the fibers.
Place the square onto a double thickness towel and roll the towel over the swatch so that it becomes wrapped up like the jam in a swiss roll.
Push down hard on the towel, the aim being to squeeze as much water out of the swatch and into the towel as possible.
Extract the swatch and shake it gently to help it return to its natural size and get rid of any creases.
Either leave it the square to dry as it is, or use pins on a blocking board (or towel or duvet) to get the swatch into a nicer square shape. To do this, place a pin at the mid-point on each side, taking care not to stretch the swatch beyond its natural size. Then place pins at each corner, pulling them out to a square shape. Add more pins to the sides to keep them straight if necessary.
Leave the square to dry completely.
Measure your gauge
Place a ruler over your swatch and, without stretching it, count the number of stitches in 10cm (or 4inches).
Then do the same for the rows. This is your stitch and row gauge.
Decide whether you have the right gauge
If your swatch matched the required gauge in the pattern, then hurrah, your swatching is done.
If you're a stitch out—or even half a stitch—and you want your item to fit, you'll need to make a new swatch with a different needle size.
If you have too many stitches in 10cm, then your finished garment would be too small, so you should try a needle size bigger.
If you have too few stitches in 10cm, then your finished garment would be too big,and you should try a needle size smaller.
If you're finding it hard to get the right gauge, then it's worth trying with needles made with a different material, e.g. if you can't get gauge with metal needles, try wooden, or acrylic.
Does my gauge really matter that much?
The amount of variation in gauge between knitters is pretty astonishing, so you can't just assume that everyone knits about the same.
If you're wondering if it's worth worrying about 1 stitch difference over 10cm, think about it over the width of a sweater. You might cast on 100 stitches in a worsted weight yarn to knit the back of a cardigan in a smallish size. 100 stitches should give you a width of 100/20 * 10 = 50cm across the back.
If you knit the cardigan at your gauge of 19 stitches per 10cm, the finished width will be 100/19 * 10 = 52.6cm. So that's an extra 2.6cm (1") in the width. Double that when you include the front, and you've just made something the next size up.