Woad Body Paint
Northern British warriors of old would paint themselves blue prior to going into battle, using a dye drawn from the woad plant. To look like a Braveheart extra (or indeed, Mel Gibson), you will need to convert your woad plants into dye.
First, find your plants. Seek out satis tinctoria, native to Northern Europe and parts of Asia (see the writeup below by JediBix783). To extract the dye, you should first finely chop up the above-ground parts of the plant, lightly pack the bits into glass jars and add boiling water until all the plant material is covered. Leave this mess to stew for an hour, then strain off the infusion and add an alkaline solution such as ammonia or lye. The more scientific among you will want to check for a pH in the region of 9, but higher values will not affect the outcome, only be wasteful of chemicals.
Aerate the solution by beating thoroughly for about 15 minutes (an old egg whisk will do, as few people like blue food). Be careful to wear rubber gloves and old clothes at this point, and watch where you do it - remember that you are dealing with a dye which will stain almost anything.
You are now almost ready to go - pour the liquid into jars and leave to settle. As time passes, the liquid separates into lighter and darker fractions - carefully pour off the lighter part and repeat until no more clear liquid appears. Finally, reduce the liquid in a non stick pan over a low heat until you have a dark blue solution.
Now you are ready to become the very picture of a fierce Pict warrior (sorry). The ancients mixed the dye with fats - the oil from sheep's fleece was a favourite, but any alcohol or oil-based substance will suffice. Apply to the skin and you're ready to rock!