My boss at a previous employer was Japanese, his wife was American, they lived in Germany, and so their 3 sons were already fluent in English and German and had a good grasp of Japanese. My boss decided to send them to a French-speaking school. According to my boss, they picked up French pretty quickly and didn't have any further problems. I don't know how it worked out long term for them - hopefully fine!
That's just an interesting example that I thought I'd throw in there - as for my opinion, it's based on my partner's and my efforts to bring up our children bi-lingual in German and English in the UK. The kids are 6 and 4 and so far, so good. At the moment after spending 2 weeks in Germany, they are chatting fluently in German with each other. We do notice that they lag slightly in English behind the 2 or 3 bright kids in their school and nursery classes who we have decided are the 'reference' English children we compare our with. Apparently this disadvantage disappears once their vocabulary has matured.
The nursery linguistics expert talked to us about non-English mother-tongue children and gave us her opinion that confirms what some of the other answers say. Apparently as they learnt to talk themselves, hearing 2nd or 3rd languages is very beneficial. She also told us that to gain fluency, the child should be exposed to the 2nd language for at least 40 hours per week.
My partner and I achieved this by making German our house language - even though mine is a bit poor. I was dubious about the benefit I was bringing with my German, but it seemed to help. My daughter now corrects my German!
Again as others say, songs, audio books and TV are all useful and helped us achieve that 40 hour mark.
For me, it was clear that my partner's mother tongue was the 2nd language of choice (in fact it is competing to be the 1st language) but for you as monolingual people, I would recommend taking the plunge yourselves and learning a second language too. You could find a lot of synergies in the efforts you are making for your child - you could read books for her in that language yourself, you could go along to foreign-language play groups and actually converse in that language yourselves with the adults there, you could go on holiday to that country and actually get by with the locals etc etc.
By the way, with all this concentration on language, don't forget how beneficial to mental development music is too. So give her a bit of Brahms or Chopin in between the French / German / Mandarin....
Good luck!