From StrategyWiki, the free strategy guide and walkthrough wiki

Throughout the game you will find records hidden in the stages, records you collect will be added to your collection and you will able to listen to them whenever you want, providing you've unlocked the Music Player NPC. When you beat the game and start a New Game+ you will also be able to select a record to be played as your BGM for stages.

Record	Stage	Location
BGM 01 Prinny Action	N/A	Collect 20 Lucky Dolls
BGM 02 Nest Of The Holy	N/A	Collect 10 Lucky Dolls
BGM 03 1st Impression	N/A	Collect 30 Lucky Dolls
BGM 04 Dance With Me	N/A	Collect 60 Lucky Dolls
BGM 05 Green Labyrinth	High Tome Forest 7 Hours Left	Underneath the third checkpoint, go to the carpet right before the checkpoint and jump down, it'll be to the right.
BGM 06 Tower of Ice	Death's Watchtower 6 Hours Left	Go through the stage until you reach the scarecrow with the 'Danger' sign, then go to the right edge of the platform the scarecrow is on and it'll be right below you, fall down and jump to it.
BGM 07 Leaden Roulette	Magma Hideout 9 Hours Left	Go through the stage until you get to the scarecrow with the 'Danger' sign at the end of the stage, go to the left end of the platform its on and fall down, there will be a ledge far below on the right with the record on it, careful of the Genin hanging from the wall above it.
BGM 08 Brave Heart	Moab Fortress 8 Hours Left	Before the hill leading to the boss gate, go to the first of the two tan Idol Buckets at the end of the stage, destroy the tan Idols and jump from their platform to the wooden platform above, from there jump and bounce off the Gargoyle and onto another wooden platform above him, then continue up bouncing off the next three Gargoyles and then jump to the Magic Carpet with the record.
BGM 09 Sweets Palace	Sweet Palace 2 Hours Left	At the final boss gate of the stage (after Hoshikage) its high above the boss gate, use the nearby tan Idol Bucket to bounce up to it.
BGM 10 Dark Soul	Black Dessert Desert 3 Hours Left	After the third checkpoint on top of the wall that the Gargoyles are on.
BGM 11 Nobody Knows	Martial Tower	Above checkpoint eight, bounce off the tan Idols to the left to get to it.
BGM 12 Going My Way	Martial Tower	Above you when you start, kinda hard to miss.
BGM 13 Flying Chorus	Martial Tower	Follow the path after checkpoint three, bounce your way up the wall with the Gargoyles, keep going until you get to three Druids lined up vertically, bounce your way up and its above the highest of the three. The Druids are right before checkpoint four.
BGM 14 Last Celebration	Martial Tower	After the Final checkpoint (12th) continue along the path upwards towards the end until you come across the Shadow Master (Ninja) the record is in the middle of the hole right past him.
BGM 15 Night At the Opera	N/A	Collect 40 Lucky Dolls
BGM 16 Beyond the Aurora	Aged Sage Altar 4 Hours Left	In the air above CHEFBOT-9000 (Bounce off his head to reach it).
BGM 17 Makai Casino	Demon Sea Aria 10 Hours Left	When you get to the tan Dolls after the line of Ghost Fruits (right after the second checkpoint), jump up and bounce off them to get to a platform placed high above the ground, follow the path up from that platform and it'll be on a cloud at the end of the path.
BGM 18 Monster Beat	Sweet Garden 1 Hour Left	After the fourth checkpoint, above a Trigoyle, theres a Succubus flying near the Trigoyle and Zombies under it.
BGM 19 Breakdown	Martial Tower	After checkpoint ten continue through the level until you reach the long path going up where you bounce back and forth on the Gargoyles, near the end of the path of gargoyles, its above the one at the top of them on the right. Its directly below checkpoint eleven.
BGM 20 Heartfull Time	Asagi Mode Chapter 4	Above the third Trigoyle right after the second checkpoint.
BGM 21 Witch Walking	Asagi Mode Chapter 2	Way up above the boss gate, bounce off the tan Idols to reach it.
BGM 22 Hello! My Dream	Asagi Mode Chapter 6	Take the path below the third checkpoint and go through the tower entrance, its above a sleeping Orc, the jumps to get to the tower entrance are a little tricky though.
BGM 23 Asagi Metamorphose	N/A	Collect 120 Lucky Dolls
BGM 24 Modern Girl	Nethergrasslands 5 Hours Left	Get on top of the tower on the left of the third checkpoint, then jump down to the right and bounce off of the Trigoyle and then land on the carpet, then follow the path across the next few carpets and you'll find it.
BGM 25 Ganbare Onna No Ko	N/A	Collect 50 Lucky Dolls
BGM 26 You Go Girl	Asagi Mode Chapter 7	Above the tank near the end of the stage, use the tan Idols that are below and to the left to bounce up to it, its just a bit above the Sundae above the Gear Metal Tank.
BGM 27 Footsteps of a Demon	Asagi Mode Chapter 5	Get to the platform high above the flying vehicle and it'll be right above the three Sundaes next to the Archer.
BGM 28 The Great Wilder	N/A	Collect 90 Lucky Dolls
BGM 29 Ode to Laharl	N/A	Collect 80 Lucky Dolls
BGM 30 Etna Rock	N/A	Collect 110 Lucky Dolls