Legal? Well, it's a grey area, let's put it that way. It's doubtless true that a lot of the music stuff posted on YouTube is illegal (YouTube's own guidelines tell us not to upload copyrighted material, but people do it all the time). As for YouTube Downloader, download.com doesn't provide illegal software as far as I know, and in any case what you'd be doing isn't 'file-sharing' - you're simply downloading material which has been made publicly available.
Incidentally, another way of finding MP3 files is to use mp3skull.com - just a case of registering (free) and searching for the song(s) you want. Not everything is there, but it has rarely let me down.