For App Store, try this: 兔小贝儿歌 There're songs, stories and poems. Can watch online or choose to download. For YouTube, try searching: 贝瓦儿歌 or 贝瓦故事 (If you can read Chinese well, can get more learning resources from their website: beva.com)
I look at 贝瓦儿歌 as well but I also bought a CD which plays mandarin nursery rhymes in the car for my boy. these CDs should be relatively cheap in the neighbourhood as I bought mine for 3 at $10!
The Mandarin Mandarin Bilingual Centre youtube channel has pretty good storytelling videos. The narrators are very animated! https://www.youtube.com/channel/UCyjRzHp9InPAE2vKoJ7f_Aw
I used to have FeedMe Chinese. Here's a bunch of recommendations too! http://haomama.us/tag/kids-chinese-apps/
Pink Fong app has some Chinese songs that can download. My son likes it a lot.