Are some animals, like dogs and cats, color-blind and how do we know that?
TL;DR: We have a good physiological understanding of how eyes work, so by examination of other species' eyes, we can tell a lot about what colours they are capable of seeing.

First, a little bit about the physics of colour

Light is made of photons, and each photon has a wavelength. The distribution of wavelengths coming from sunlight looks like this (wavelengths on the x axis):



Any perceived 'colour' is some sort of summary of the wavelengths of the photons which get into an animal's eyes.

Now, a little about colour perception

There are cells in the eyes which respond to being hit by photons: these are called rods and cones. Colour vision is principally achieved using the cone cells, which have a peak sensitivity at one particular wavelength, and are less sensitive at other wavelengths.

We (non-colourblind humans) have three different types of cone cell, sensitive to photons with wavelengths of 560, 530, or 420 nm, corresponding to the peak sensitivities of three different types of light-sensitive opsins which are present in cone cells. Other types of opsin exist in rod cells (Rhodopsin) and our circadian-rhythm entrainment (melanopsin), but the three different opsins in our cone cells are responsible for our colour vision. Because we have three different types of cone cell, we are referred to as 'cone trichromats'. The sensitivities of the three cone types overlap a bit, looking like this when plotted over the visible spectrum:



When cone trichromats perceive colour, what we're doing is taking the information on how active each of our different types of cone cell are, and using that to infer how many photons there are of each wavelength in the light that hits our eyes.

Of course, cone trichromats can't possibly summarise the whole diversity of wavelengths that are coming into their eyes using just three different measures of intensity - the line is way too complicated to summarise from three points. Also note that for humans, there is no cone cell that is sensitive above about 700 nm, or below about 400 nm. This means that we simply can't see differences in the infra-red or UV parts of the colour spectrum.

How does this all relate to colour-blindness in animals?

It is fairly simple to test the peak sensitivity of a cone cell: you take an eye from a freshly-dead animal, hook up an electrode to a cone cell, and then provide light of different wavelengths, and measure what wavelength causes the cell to 'fire' the most. If you repeat this with a large number of different cells, you can confidently determine how many different types of cone cell the animal has, and what wavelengths those cone cells are most sensitive to. This experiment (or similar ones) has been done for many different species, so we have a good background knowledge of what colours different species are capable of seeing.

Many species, including most non-primate mammals, have only two types of cone cell (i.e., they are cone di-chromats, as against non-colourblind humans, which are cone tri-chromats). This doesn't mean they see no colour, but it does limit the types of colour they are able to see. Many tools exist to simulate the visual ability of cone dichromats, for instance here, or here for browsers without flash support. These tools simulate human vision with different numbers of cone cell types. When comparing across species, it is important to remember that both the number of types of cone cell, and the peak sensitivity of each type, may be different, so the tools do not capture the full range of possible colour-perception abilities across species.

There are also cone tetrachromatic (four types of cone cell) and pentachromatic (five types) species. The record appears to be held by mantis shrimps, which have sixteen different types of cone cell. These species can in principle see a greater diversity of colours than cone trichromats.

Does colourblindness present an evolutionary problem?

Not necessarily. Compared to cone tetrachromatic species, humans are 'colourblind', and it seems to have very little impact on our day-to-day survival. Similarly, most colourblind humans (i.e., with one or more types of cone cell disabled compared to non-colourblind humans) get along perfectly fine - a special test is needed to detect colourblindness in humans. If trichromatic vision gives no particular survival advantage, there is no reason to think that it will be favoured by evolution.