I ask this question every few years, and the answer has so far remained: "you can't".
I thought about trying to write something to scrape MetroLyrics since their HTML isn't too bad, but wow what a pain in the ass. I don't want to do that. (Before you suggest buying the MetroLyrics app, read the reviews: it's bullshit.)
There are hundreds of apps out there that will display a pop-up window of the lyrics already contained in the ID3 tags of the currently-playing song; and some of them try to search the web for lyrics; but the dozens of them that I've tried have sucked at this, badly. Also, none of them will do it in bulk. Do you use one that doesn't suck?
Since most of my library doesn't have lyrics, I want to bulk-download as many as possible, non-interactively, without having to play each song first, and without having to click, like, 50,000 times.
It's hard to search for this shit because it's a morass of spammers and "free ringtone" malware.
Apparently the music labels don't offer embedded lyrics within the legal MP3s sold by Amazon and Apple because that would undermine their profitable sideline of suing aforementioned lyrics malware websites.
Update: This year, the current best option appears to be Get Lyrical. It's not very good, but it seems to be the best of a bad set of options. It gets its info from Lyrics Wikia, from which several of the other apps also pull.
Update, 2013: I wrote my own.
