Palomino is a color based on chestnut, with a dilution gene causing the body color to become a gold or dark cream color, and the mane and tail to be white. It does not breed true, and is most often bred by crossing a chestnut horse with a cremello horse. For details of the genetics, read this page.
Similar colors in appearance, but not to be confused with palomino, are flaxen chestnut, in which the body is a reddish brown and the mane and tail are blond; and the dilutions called cream or cremello, perlino and champagne, in which the entire body, mane and tail are an even white, beige, cream or gold color. The Haflinger and Belgian Draft are two breeds that often appear to be palomino, but are actually flaxen chestnut. Similar appearance, different genetics.
In cold climates the winter coat of the palomino may appear white or cream colored, darkening to gold again in summer.
Arabian horses don't come in palomino, as the dilution gene doesn't exist in Arabians. Horses that appear to be palomino Arabians are (as far as I've ever seen) part Arab (even 15/16ths Arab) and the dilution was introduced by another breed.
It has been thought that Thoroughbreds don't carry dilution either, as it is very rare, but this page shows a cremello and some palominos.
Here are some examples of palomino in various breeds:
Photo above: Kvetina-Marie on flickr