If they don't take a Domain, they get full level Animal Companion.
If the Druid takes the Domain option, and chooses Animal Domain, it works like a Cleric, with level adjustment.
Both stack with the Cleric levels with Animal Domain
(Animal Domain from both Classes stacks directly, so you don't have to subtract 3 twice)
The wording could probably be more exact about that, since if you are a Druid with a Domain,
and you read the Animal Companion language that says "these are calculated off your Druid level", (no mention of adjustment)
you want to say "Hey, I have Druid levels, why don't I just use those!?"
Hope I've solved your quandary... ;-)
------------------------------------------------------------------
Animal Companion classes stack, and Paladin Mount counts as an Animal Companion.
I'm not 100% certain about the special abilities that Paladin Mounts gain (Celestial template, INT, etc).
If one class' Companion feature has special bonuses and gives you a restricted list of Companions,
then it is plausible that you can only apply those special bonuses to normally eligible Companions. (i.e. choose a new companion)
On the other hand, Companion abilities, which Mount functions as, are meant to stack,
so if the Mount is functioning as a Companion, and stacks with other Classes' Companion levels,
(so you can't have more than 1 companion normally)
it makes sense that the single Companion IS the Paladin's Mount and all bonuses/abilities apply to it normally.
(so you don't need to choose a new companion)
I would go with the latter interpretation, which means that dipping in Druid opens the entire Companion list to you.
Per RAW, the Paladin ISN'T actually literally restricted in choice, even though the language strongly suggests what is the norm, albeit in PFS they do make you stick to that list... But if you do dip in Animal Domain Cleric, then the entire list should be open, IMHO, and special Paladin abilities should apply to it.
I suggest hitting the FAQ button, Paizo has made clear that Companion classes stack,
but they haven't dealt with how to resolve any bonuses that come from one class' specific Companion ability...
From: Druid Nature Bond, Core Rule Book, Page 50
Nature Bond (Ex): At 1st level, a druid forms a bond with
nature. This bond can take one of two forms. The first is a
close tie to the natural world, granting the druid one of the
following cleric domains: Air, Animal, Earth, Fire, Plant,
Water, or Weather. When determining the powers and
bonus spells granted by this domain, the druid’s effective
cleric level is equal to her druid level. A druid that selects
this option also receives additional domain spell slots, just
like a cleric. She must prepare the spell from her domain
in this slot and this spell cannot be used to cast a spell
spontaneously.
The second option is to form a close bond with an
animal companion. A druid may begin play with any of
the animals listed in the Animal Companions section
beginning on page 51. This animal is a loyal companion
that accompanies the druid on her adventures.
Unlike normal animals of its kind, an animal
companion’s Hit Dice, abilities, skills, and feats advance as
the druid advances in level. If a character receives an animal
companion from more than one source, her effective druid
levels stack for the purposes of determining the statistics
and abilities of the companion. Most animal companions
increase in size when their druid reaches 4th or 7th
level, depending on the companion. If a druid releases
her companion from service, she may gain a new one by
performing a ceremony requiring 24 uninterrupted hours
of prayer in the environment where the new companion
typically lives. This ceremony can also replace an animal
companion that has perished.
From: Animal Domain, Cleric, Core Rule Book, Page 41
Animal Companion (Ex): At 4th level, you gain the service
of an animal companion. Your effective druid level for this
animal companion is equal to your cleric level – 3. (Druids
who take this ability through their nature bond class
feature use their druid level – 3 to determine the abilities
of their animal companions).
From: Divine Bond, Paladin, Core Rule Book, Page 63
Divine Bond (Sp): Upon reaching 5th level, a paladin
forms a divine bond with her god. This bond can take one of
two forms. Once the form is chosen, it cannot be changed.
...
The second type of bond allows a paladin to gain the
service of an unusually intelligent, strong, and loyal
steed to serve her in her crusade against evil. This mount
is usually a horse (for a Medium paladin) or a pony (for
a Small paladin), although more exotic mounts, such
as a boar, camel, or dog are also suitable. This mount
functions as a druid’s animal companion, using the
paladin’s level as her effective druid level. Bonded
mounts have an Intelligence of at least 6.
Once per day, as a full-round action, a paladin may
magically call her mount to her side. This ability is
the equivalent of a spell of a level equal to one-third
the paladin’s level. The mount immediately appears
adjacent to the paladin. A paladin can use this ability
once per day at 5th level, and one additional time per day
for every 4 levels thereafter, for a total of four times per
day at 17th level.
At 11th level, the mount gains the celestial template (see
the Pathfinder RPG Bestiary) and becomes a magical beast
for the purposes of determining which spells affect it. At
15th level, a paladin’s mount gains spell resistance equal to
the paladin’s level + 11.
Should the paladin’s mount die, the paladin may not
summon another mount for 30 days or until she gains
a paladin level, whichever comes first. During this 30-
day period, the paladin takes a –1 penalty on attack and
weapon damage rolls.
I know you didn't ask about the Paladin, but I will squeeze it in there.
From Anmal Companions, Core Rule Book, Page 51:
Class Level: This is the character’s druid level. The
druid’s class levels stack with levels of any other classes
that are entitled to an animal companion for the purpose
of determining the companion’s statistics.
=====================================
So, to answer your question, a Cleric (Animal Domain) 4, Druid 1 would have an Animal Companion as a second level druid. You would then use the Animal Companion chart to determine the Animal Companion's abilities.
To add in the Paladin Level question posed by Quandary:
The rules specify that the Divine Bond applies to a mount. They would not stack with an animal companion that was not capable of being a mount. Note that the rules also specify that the mount need not be a horse, pony, etc. The Special Abilities a Paladin's mount gets are ranked by Paladin Level, not Animal Companion HD. So the divine bonded mount will get the templates and special abilities as the Paladin Level meets the required level. So, for instance, since a Paladin does not gain her Divine Bond until level 5:
Druid 3 Paladin 4 would have an Animal Companion as a level 3 Druid.
Druid 3 Paladin 5 would have an Animal Companion as a level 8 Druid, because the Paladin now has the Divine Bond ability.
A Druid 3 Paladin 8 has an Animal Companion as a level 11 druid, but the Paladin level is still only 8, so the paladin does not yet gain:
At 11th level, the mount gains the celestial template (see
the Pathfinder RPG Bestiary) and becomes a magical beast
for the purposes of determining which spells affect it.
because the paladin level is still only 8.