There is a possibility of rainbows appearing naturally on other celestial bodies that have sufficient water vapor or a large number of water droplets in their atmospheres, or indeed gases or droplets of other molecules that are capable of acting upon the light from the Sun (or other sources) as tiny prisms and refract it to its visible components (different wavelengths). Another possibility is also mineral dust scattered in the atmosphere, or indeed in planetary rings:

Scatter plot of refraction of various transparent minerals and their density (source: physics.info)
Problem is, we don't really know which celestial bodies in our Solar system might that be. Mars has possibly too thin atmosphere and not enough water vapor (210 ppm) for any such effect to be really noticeable, and we don't know enough about atmospheric conditions of other planets and their moons.
But there are other possibilities. For example Titan, one of Saturn's moons, has liquid methane (refraction index of 1.29):

Titan's layers of atmosphere in the UV + visible spectrum, image from the Cassini–Huygens spacecraft (source: Wikipedia)
Even stronger case for possible rainbow effect forming on the surface of Titan comes from Cassini and Huygens observations, indicating that Titan might have a pretty complex weather system and precipitation in the form of liquid methane rain:
Conditions in Titan's troposphere are near the triple point of
methane, the second most abundant component of its atmosphere. Our
understanding of Titan's lower atmosphere has shifted considerably in
the past decade. Ground-based observations, Hubble Space Telescope
images, and data returned from the Cassini and Huygens spacecraft show
that Titan's troposphere hosts a methane-based meteorology in direct
analogy to the water-based meteorology of Earth. What once was thought
to be a quiescent place, lacking in clouds or localized weather and
changing only subtly on long seasonal timescales, is now understood to
be a dynamic system with significant weather events regularly
occurring against the backdrop of dramatic seasonal changes. Although
the observational record of Titan's weather covers only a third of its
30-year seasonal cycle, Titan's atmospheric processes appear to be
more closely analogous to those of Earth than to those of any other
object in our solar system.
(Source: Titan's Methane Weather, Annual Review of Earth and Planetary Sciences, Lowell Observatory, May 2012)
Update: In July 2011 a glory, a rainbow-like feature has been observed for the first time on another planet by ESA's Venus Express probe:
The atmosphere of Venus is thought to contain droplets rich in
sulphuric acid. By imaging the clouds with the Sun directly behind the
Venus Express spacecraft, scientists hoped to spot a glory in order to
determine important characteristics of the cloud droplets.
They were successful. The glory in the images here was seen at the
Venus cloud tops, 70 km above the planet’s surface, on 24 July 2011.
It is 1200 km wide as seen from the spacecraft, 6000 km away.

This simulated view shows how a glory would appear on Venus (left) versus Earth (right). (Source: Nature.com)
It's beyond me why this took nearly 3 years to make its public debut in April 2014, but here we have it, a rainbow on another celestial body than Earth:

An optical effect called a glory seen by the Venus Express probe from an altitude of 6,000 kilometres. The false-colour image
is composed of images at ultraviolet, visible, and near-infrared wavelengths taken ten seconds apart, so that they do not
overlap perfectly. (Caption credit: Nature.com, Image source: ESA)
Discovery of this glory isn't merely a pretty sight, but gives Cytherean atmospheric physicists clues about its composition, among other things. For example, New Scientist article, referencing Icarus, DOI: 10.1016/j.icarus.2014.01.030 (Markiewicz et al.), puts it like this:
The team found that sulphuric acid droplets alone
cannot explain the glory, but droplets coated with elemental sulphur
or mixed in with ferric chloride fit the data well.
"This could be the so-called unknown absorber that people had been trying to identify for years," Markiewicz says. "We cannot say for
sure, but we can say that this is one more piece of the puzzle for the
whole thing."