The song is mentioned several times in the books, but we get the complete lyrics to the song in the third book A Storm of Swords. Here is a list of the song's appearance in the books so far from the excellent A Wiki of Ice and Fire article (which also has the complete lyrics):
Spoilers added for TV watchers.
A Clash of Kings
The song is sung at the harvest feast at Winterfell.
A Storm of Swords
Tom of Sevenstreams sings it with Hot Pie on the ride to the Inn of the Kneeling Man. When Tom wants someone to sing with, Hot Pie tells him he knows the song about the bear. Tom starts to sing it and Hot Pie joins in lustily, even bouncing in his saddle a little on the rhymes. Arya Stark is astonished; Hot Pie has a good voice and sings well, she thought all he could do was bake.
During the grim march back to Craster's Keep after the Fist Grenn tries to encourage Samwell Tarly to keep marching by telling him to sing a song in his head. Sam knows a hundred songs but is so terrified he cannot think of any. Grenn suggests "The Bear and the Maiden Fair" and starts to sing it - but Sam begs him not to as it makes him think of the hideous wight-bear that had come at them at the Fist.
It is sung by Butterbumps at Sansa Stark's dinner with Margaery Tyrell and Olenna Redwyne to cover the conversation about Joffrey Baratheon.
Greatjon Umber sings it, drunkenly, at the Red Wedding.
During the Battle of Yunkai Ser Barristan Selmy tells Daenerys Targaryen that Robert Baratheon liked songs that made him laugh. Barristan adds that Robert only sang when he was drunk, and then by that point one of the songs was likely to be the "The Bear and the Maiden Fair".
Feast for Crows
It is sung by Dareon on the voyage to Braavos.
A Dance With Dragons
The song is sung by Abel for Barbrey Dustin during a meal at Winterfell. In Meereen Tyrion Lannister realizes that Ser Jorah Mormont is doomed if purchased by Zahrina. Tyrion manages to get the slave overseer Nurse to convince Yezzan zo Qaggaz to purchase Jorah by lying and telling Nurse that Jorah is part of their show - the bear and the maiden fair. Jorah is the bear, Penny is the maiden, and Tyrion is the brave knight who rescues her. During their bondage Tyrion notes that Jorah has not adapted well. When called upon to play the bear and carry off the maiden fair, he has been sullen and uncooperative, shuffling lifelessly through his paces when he deigns to take part in their mummery at all.