I know this is sort of a silly question, but the other day when walking in the park, I saw a squirrel and said, "Hello, Mr. Squirrel". I know for me, my choice of Mr. over Mrs. was random, or at least influenced by factors outside of language, but it got me thinking. I wonder if in a particular language, if squirrel were feminine, would a speaker of that language automatically use "Mrs. Squirrel"?
No, not anymore so than in English.
In German, Herr Pferd and Frau Pferd both work. Pferd is neuter, and I think that is almost the answer right there: so-called grammatical genders are just noun classes, in IE languages there are often three classes, not two, so how would a strict 1:1 mapping to two forms of address even be possible?
Bär is masculine. Frau Bär is fine, and Frau Bärin is a bit odd, Herr Bär is of course fine.
But Herr Kuh is unnatural, not because of the grammatical gender of the noun, but because of the actual gender of a cow in real life. Just as in English one would probably not say Mr Cow, and one would definitely not say Mrs Rooster.
It will depend on the language, but only because it depends on whether and how strictly a word specifically refers to only one gender of a species. (That probably varies within a language too, given speakers' varied exposure to animals in nature and agriculture.)
For example, in German or Russian there are specific words for female and male cats, a bit like chicken and rooster, and note that female is the default, for an unknown individual or mixed group. Herr Katze and Herr Kater are roughly equally frequent on the web.
There are more complications to all of this, for example in Spanish the word for cat, gato, default male, can be feminised to gata, but the word for cow, vaca, cannot be made vaco for bull, so there is señora gata, and señora gato, but there is no señor vaco.
To really make a point that grammatical genders are just arbitrary noun classes, consider that in such languages even inanimate nouns like Automobil or abstract nouns like Situation have a gender, and speakers do not even think about it.
In Portuguese there are animals for which there are two different names, one for the male, and one for the female:
O touro (bull) - a vaca (cow)
O cavalo (horse) - a égua (mare)
Other animals are referred by just one name, but it inflects by gender:
O gato - a gata (cat)
O porco - a porca (pig)
Still others have just one name, that does not inflect by gender. Those have a fixed gender, irrespective of the sex of the animal:
A onça (jaguar)
A doninha (weasel)
O elefante (elephant)
O furão (ferret)
And then there are a few names that do not inflect, but accept articles of either gender, according to the sex of the animal:
O jabuti - a jabuti (tortoise)
The third and fourth categories are more commonly composed by names of non-domesticated animals - and the fourth is more usual among borrowings from Tupi-Guarani.
But the issue is somewhat blurred. Some would say that "elefante" does have a feminine form (and then disagree whether it is "elefanta" or "elefoa" - placing the word in the second category above - or "aliá", which would make it an instance of the first category). And definitely there are cases where there is inflection, but one of the genders is more or less automatically used when the sex of the animal is unknown - "raposa" (fox) does have a masculine form, "raposo", but the feminine is used whenever the sex of the animal isn't important.
Now, a use such as "Seu Esquilo" (Mr. Squirrel) is unusual - it is either children talk or a peculiar subset of the literary register, pertaining to fables or fairy tales. And then the rules are much laxer than in standard or colloquial register. If the animals come in couples, it would often be natural to call them "Dona Onça" and "Seu Onço", even though the latter would be weird in colloquial speech. This is however very irregular, and the use of one of the forms may sound weird even in a fable ("Seu Furão", ?"Dona Furona"; "Dona Zebra, ?"Seu Zebro"). Also in fables, the modern (and somewhat colloquial) masculine "Seu" could possibly be replaced by the archaic "Dom" - as in "Dona Baratinha e Dom Ratão").
So, in the case in point, I think the most natural thing would be to call the squirrel "Seu Esquilo", unless for some reason one would assume it is a female (the word does have a feminine form, "esquila"). If it was a fox, it would be more natural to call it "Dona Raposa" unless for some reason it was assumed to be a male.
If it was a jaguar, it would be "Dona Onça", with the alternative "Seu Onço" only if we intended to stress it was a male, if we are telling a fable; in colloquial or standard Portuguese we would call a male jaguar "onça-macho" (and use the feminine articles and adjectives - "a onça-macho estava furiosa".)
I think the previous answers missed the point by focusing on animals, which have a biological gender (apart from the gender assigned to the noun).
As a native speaker of Spanish, if I wanted to address, say, a fork, my first instinct would definitely be to say Señor Tenedor as opposed to Señora Tenedor. But if I wanted to get the attention of, say, a napkin, I would say Señora Servilleta and not Señor Servilleta.