First, instead of a headband of vast intelligence, I recommend the circlet of speaking (4,800 gp; 0 lbs.), which grants an animal wearing it the ability to speak 1 language yet doesn't increase the animal's intelligence. Although slightly more expensive than the cheapest headband, the circlet is, in many ways, superior if you want a talking animal that can still be trained; it neatly sidesteps the intelligent animal's language issues detailed below. That said...
Yes, were an animal to wear a headband of vast intelligence +2 et al. that animal could learn a language were its Intelligence score to have gone from 1 or 2 to at least 3
Such an animal could learn to understand a language but couldn't learn to speak. The section on Intelligent Animals says that
Increasing an animal's Intelligence to 3 or higher means it is smart enough to understand a language. However, unless an awaken spell is used, the animal doesn't automatically and instantly learn a language, any more than a human child does. The animal must be taught a language, usually over the course of months, giving it the understanding of the meaning of words and sentences beyond its trained responses to commands like "attack" and "heel."
Even if the animal is taught to understand a language, it probably lacks the anatomy to actually speak (unless awaken is used). For example, dogs, elephants, and even gorillas lack the proper physiology to speak humanoid languages, though they can use their limited "vocabulary" of sounds to articulate concepts, especially if working with a person who learns what the sounds mean.
So the vague description above of how to teach an intelligent animal language all but says not to bother trying. Further, the most obvious way of improving an animal—taking the animal on adventures so it can gain XP—isn't an option, either, because animals, like most NPCs (cf. the feats Leadership and Squire), just don't earn XP.
Thus while the intelligent animal has the potential for language—all it would take is but 1 rank in the skill Linguistics for the animal to understand a language—, the intelligent animal lacks the ability to gain that rank. It's stuck with what it has.
However, to use what it has, the creature can employ the rules for retraining its skill ranks. By spending a paltry sum and as long as a several weeks, a creature can allocate its accumulated skill ranks differently. For an intelligent animal, this lets it put that minimum 1 rank in the skill Linguistics and understand a language.
Example
A common cat has 1 Hit Die and while wearing a headband of vast intelligence +2 an Intelligence score of 4. The cat murders a family of commoners and takes the family's treasure, as is a cat's wont. The cat spends 50 gp and 5 8-hour work days avoiding strenuous activity and, afterward, reallocates its skill rank from the skill Perception to the skill Linguistics, therefore learning the language of its choice.
Unfortunately, as they have no starting language, most animals are barred from using the retraining rules to learn a New Language independent of their ranks in the skill Linguistics because
Each language [gained through the New Languages section of the retraining rules] requires a trainer who shares a language with you and knows the language you want to learn, or a book written in a language you know that explains the basics of the language you want to learn.
Emphasis mine, and these rules make me sad. However, the DM could allow a trainer with the ability to speak with animals for 8 hours a day and who was willing to do so be an intelligent animal's language trainer. Extending the duration of a speak with animals effect from its typical 1 min./level to at least 8 hours is not impossible (e.g. a friendly high-level character's familiar that can both speak a language and speak to others of its kind, a creature with the animal domain and the pelt of the beast, feral speech a la wizard or witch). This New Language retraining, were it available, would cost the intelligent animal 200 gp and occupy both the intelligent animal and its trainer for 20 8-hour work days that must be otherwise absent of strenuous activity.1
Strangely, an animal with an Intelligence score of 1 or 2 can put ranks in the skill Linguistics, doing so through retraining as described above or just using its native skill ranks.2 The animal, however, still isn't "smart enough to understand a language," so what, exactly, these ranks in the skill Linguistics do for an animal is unclear. (Animals that are also animal companions have a skill list that prevents the animal companion from putting ranks into some skills at all.3 Such a creature can't put ranks in the skill Linguistics until it has an Intelligence score of at least 3.)
Yes, a headband of vast intelligence +2 et al. that's imbued with the skill Linguistics and that raises an animal's Intelligence score to at least 3 grants the animal the ability to understand a number of languages equal to the animal's Hit Dice.
Such languages are probably picked by the item's creator, although this isn't entirely clear. An animal wearing such an item wouldn't need to "be taught a language, usually over the course of months," nor retrain as described above. Such a creature still can't speak, however.
No, a typical thrush or typical raven (or parrot) wearing a headband of vast intelligence +2 et al. that learned a language would not be able to speak that language.
Only when these creatures become familiars do they gain the supernatural ability to speak but 1 language. In fact, only if further effects permit is such a familiar ever able to speak more than the 1 language picked when the familiar was first gained. While the familiar may be able to understand other languages (e.g. bonus languages from a high Intelligence score, its master's Linguistics skill, a headband of vast intelligence +2 et al. imbued with the skill Linguistics), the familiar will remain unable to speak those languages.
However, it's a reasonable house rule to allow a familiar with the supernatural ability to speak 1 language to speak, instead, any language it knows.
1 Undoubtedly, there's a sitcom pilot being pitched right now about a good-hearted but down-on-his-luck wizard with the arcane discovery feral speech who teaches Common as a First Language classes to wealthy, murderous cats at the local night wizards' school. Attention, Networks: I will pay real money to watch this show.
2 An animal's class skills are Acrobatics, Climb, Fly, Perception, Stealth, and Swim. Thus the animal can put ranks into the skill Linguistics, but won't get the bonus that comes from the skill being a class skill.
3 "Animal companions can have ranks in any of the following skills: Acrobatics* (Dex), Climb* (Str), Escape Artist (Dex), Fly* (Dex), Intimidate (Cha), Perception* (Wis), Stealth* (Dex), Survival (Wis), and Swim* (Str). All of the skills marked with an (*) are class skills for animal companions. Animal companions with an Intelligence of 3 or higher can put ranks into any skill."
