Lots of people have explained the mechanics of clearing, which it sounds like you already understand, so perhaps the missing piece is when to do it. You probably want to clear things as the very first thing in your Freebase Suggest select callback, before you fire off any of the queries to other services like Spotify (i.e. before the first $.getJSON()).
Not related to your question, but don't forget the attribution requirement of the Freebase license (not currently provided on your web site).
EDIT: Here's your code with empty added:
$('#myinput').suggest({key: "<mykey>","filter": "(all type:/music/musical_group )"
})
.bind("fb-select", function(e, data) {
$('#spotify-div').empty(); // empty the div before fetching and adding new data
$.getJSON("http://ws.spotify.com/search/1/track.json?q="+search_val, function(data) {
items = [];
$.each(data["tracks"], function(key, val) {
items.push('<li class="spot"><span typeof="MusicRecording" property="track"><p>Name: <strong><span property="name">' + val["name"] + '</span></span></strong></p> <p>Album <strong>' + val.album["name"] + '</strong></p><p> Released: <strong>' + val.album["released"] +'</strong></p><p><strong><a href="' + val["href"] +'"><i class="icon-play-sign"></i> Start Spotify</a></strong></p>');
if ( key === 7 )
{
return false;
}
});
$('#spotify-div').prepend('<h3 style="border-bottom:1px solid white;">Spotify tracks</h3>');
$('#spotify').html(items.join('</li>'));
});
});