Pr3mium, I'm inclined not to post, but I really haven't played with Audacity much. I just tried an experiment or two on a couple of youtube downloads, but they didn't pan out. I'm hoping some one a lot more sophisticated can give you specific instructions, but, just in case they don't, a couple of thoughts:
I'm guessing part of the problem is that you may be expecting too much. As you may be aware, most youtube videos are in the flash .flv format. Not known for it's audio quality. I don't know if you know this, but if you see "high resolution version" (or is it high definition? I forget what youtube says) click on that and download it. That's an MP4, and not only the video, but the audio quality is much better. If you haven't heard, both flv and mp4 what are called lossy formats, meaning some quality is lost right from the get go, and if you drop them to an mp3, it gets even worse. An, as I say, with a flash you're usually starting with a mediocre copy of the audio in the first place.
If you just want to store them on your computer, you can try converting them to .wav files, which have no additional loss. But take up quite a bit more space. In any case, all I'm saying is you might have to experiment in trying to get audio from the best quality formats and dropping them to the best format you can get away with using. You might be trying to get "blood out of a stone", but I'm hoping someone else can give you better directions.