In the case of mammals like giraffes and koalas, is that bacteria common on the plants they eat so when a baby starts to try to stick something besides its mother's milk in its mouth, it can't digest the cellulose at all the first time, but along with the cellulose, into its mouth went some cellulose-digesting flora that then begins a lifelong colony in the animal's gut? Is that about how it happens?
I would not expect this to be any different than other animals - they get the flora from the environment. Key components of the environment for newborns are:
- Birth canal
- Den / living quarters
- Skin / fur of mother, especially near the teats
- Feces of family members (animals sniff this and aren't so clean)
I don't know about ruminants, but baby rabbits (and presumably other lagomorphs) apparently acquire the necessary intestinal flora by consuming their mother's cecotropes.
 Johnson-Delaney, C.A. (2006), "Anatomy and Physiology of the Rabbit and Rodent Gastrointestinal System" (PDF)
We now know that humans acquire not only their initial gut flora but also that of the skin from swallowing and touching mother's vaginal mucus. This doesn't apply to Caesarean birth, however.
For reference, see my answer at skeptics: https://skeptics.stackexchange.com/questions/9994/do-c-section-born-babies-have-worse-immune-systems/10078#10078