There are two basic genes on which the rest of horse colour and patterning is built: the Black/Red gene and the agouti gene. Black is dominant over Red, so only a homozygous Red horse will display the red colour. A plain Red horse is "chestnut", and a plain black horse is (possibly slightly surprisingly) "black". The agouti gene is a modifier on the black pigment, restricting it to the "points", ie nose, tail, ears and feet, of the horse. Agouti is dominant, explaining the relative rarity of true black horses (they need to be homozygous for two recessive genes), and gives rise to the familiar "bay" colouration, a chestnut body with a varying amount of black hair concentrated at the extremities of the horse.
Chestnut and Bay: http://en.wikipedia.org/wiki/File:Horsescd1l-095.jpg
The next category of genes is "dilution" genes, which predictably reduce the amount of pigmentation produced in the horse's skin. There are three well known ones, dun, cream and champagne. Dun is a dominant gene that lightens Red to a yellowish colour and Black to a mousy brown, often with darker legs and a strip along the back. Bay Dun is the stereotypical colour of Przewalski's horses, the only true wild horses, and thought to be (based on cave paintings) the colour of horses pre-domestication. Another dilution gene, Cream, is interesting genetically because while it is technically dominant, it is highly dosage-dependent, ie a horse with only one Cream allele will be much darker than one with two. Thus, Red is diluted to a similar yellowish colour to Dun but without the darker markings, giving rise to the Palomino and Buckskin colours (single-allele dilution of chestnut and bay respectively) and Cremello (double dilution of chestnut). Cream can also act on black hair, but not so strongly, resulting in black horses that are slightly dark brown, and prone to sun-bleaching. Other similar dilution genes exist, and possession of two or three of them is one way of getting a "white" horse that actually turns out to be a pale cream colour when genetically tested.
Bay Dun: http://en.wikipedia.org/wiki/File:Unsortedanimal_1.jpg
Next, we look at genes that cause multicolour patterning. These are all of the form "colour-and-white" - although many of them look like a white horse with small coloured patches, genetically they take one of the above mentioned base colours and add white bits to it. These can cause a huge variety of patterns, and are another way of getting a "white" horse- these horses are actually a coloured with all-over white markings. British English uses "piebald" for a white-on-black horse and "skewbald" for a white-on-another-colour horse. The white patterning genes all add in a dominant fashion to the previously explained colour schemes, though it is possible for a horse with one of these genes to actually not display any visible white marks.
Some "white" genes are lethal when homozygous dominant- foals are born healthy and completely white but do not have a functional large intestine- this is known as Lethal White Syndrome. For this reason, genetic testing has become very useful when breeding horses with white patterning, as you can then avoid crossing two horses with one copy of the lethal white gene. Such a cross would result in, as with Mendel's pea plants, 1/4 chance of a solid coloured foal (two recessive alleles), a 1/2 chance of a white-patterned foal (one dominant, one recessive) and a 1/4 chance of a foal suffering from Lethal White syndrome. Given that the same 1/2 chance of a patterned foal is present when crossing a white-patterned and a solid horse, with no risk of Lethal White, arranging the former mating would seem negligent at best.
Small coloured spots on a white background (or more properly a white overlay with small spots of the base colour) are caused by a gene called Leopard, and cause effects stereotypical of Appaloosa horses, as shown below. There is a small "halo" around each spot where the skin is still dark but the hair growing from it it white.
Tobiano patterning: http://en.wikipedia.org/wiki/File:Irish_Tinker_horse.JPG
Sabino patterning: http://en.wikipedia.org/wiki/File:SabinoTestedNegforOLWS.jpg
Appaloosa "leopard" pattern: http://en.wikipedia.org/wiki/File:Appaloosa_stallion.JPG
The final major gene we will look at is the Grey gene. A Grey horse, regardless of what other colour genes it carries, will start off showing the colour dictated by those other genes, and then slowly fade to white hair as it gets older. A grey horse can start off any other colour combination as above, and the Grey gene is dominant. A grey horse is distinguishable from a white one by its dark skin, which will remain pigmented even when the hair growing from it has faded to pure white.
Young grey horse: http://en.wikipedia.org/wiki/File:Lippizaner_DSC02439.JPG
Older grey horse, now almost completely white-haired: http://en.wikipedia.org/wiki/File:Andalusier_3_-_galoppierend.jpg
So how *do* you get an actually white horse? There is another dominant gene which, if present, will produce a completely white coat. A true-white horse can be distinguished from cream or grey by its pink skin and hooves- compare and contrast the picture of the older grey horse above with the white below.
White horse: http://en.wikipedia.org/wiki/File:DominantWhiteHorsesD.jpg
There are of course other genes that can add on to this basic set, the most obvious being Roan (white hairs intermingled with whatever other coat colour the horse has), Sooty (similar, but with dark hairs), and Pangare, which lightens the belly and the insides of the legs.
So, putting this all together, to determine how a horse got its colour, you ask in order:
1. Is the base colour red or black?
2. If red, is the agouti gene present to cause black points?
3. Are there any dilution genes present?
4. Are there any white patterning genes present?
5. Does the horse carry the Grey gene?
As all the genes described in 2-5 are dominant, you can then work out what colour foals can (and can't) be born to horses with particular coat colours. And probably pay obscene amounts of money to studs as a result ;-)
And finally, I apologise for any misuses of terminology related to horses. I am a geneticist, not a horse person...