eyeD3で--add-imageを使えば埋め込めるらしいとはわかったのですが、最初、walkman側が埋め込み画像に限らず題名・アーティストなど全然解読してくれず（当然、eyeD3自体で各種タグが埋め込まれていることは確認）何故だーと思いつつググりました。 そうしたらこちらのサイトがヒット。
Walkman, Linux, D&D - Omong Kosong Lagi
ありがたくお知恵を使わせていただき無事動作しました。
肝心なことは、
- walkmanではid3tagのバージョンは2.3でないと認識してくれない。2.4ではだめ。
- --add-imageで与えるオプションはFRONT_COVERらしい
そういうことでした。最新のwalkmanではどうだかわかりませんが…
