I don't know any specifics about how these companies do things, but this part of what they do doesn't seem like it'd be especially hard. The various music service APIs provide ways to search their libraries for a string so you could do a reasonable first stab that way. Youtube's API provides the metadata so as long as the video has accurate metadata you can search on that.