Установите себе аимп3 и зайдите в медиабиблиотеку, и Вы увидите как этот функционал реализован. Если нужны технические подробности, то скачайте исходники какого нибудь
Banshee или что Вам больше нравиться и исследуйте то как до Вас это уже решили.
Ну и путь где искать файлы надо то все таки полюбому запоминать.
А по поводу сканирования, при первом сканировании сохранять все в БД, а потом при последующем использовании в фоновом режиме отслеживать изменения и записывать в БД.