miyaennさん
windowsで使っていたcraving explorerは、確かにwindows専用のソフトですね。
http://freesoft-100.com/pasokon/craving_explorer.html

UbuntuはOSとしての分類ではLinuxになりますので、間違いなく動作しません。
エミュレータであるwineなどで稼働するかもしれませんが、私はその情報には疎いです。

ニコニコ動画にはにこさうんどを使えば著作権どうのは別としてDownloadが可能です。

ブラウザのブックマークレットも用意されていますのでワンクリックでダウンロードできてしまいます。

にこ☆さうんど＃ convert nicovideo to mp3 online
http://nicosound.anyap.info/

また同様のサービスににこみみというものもあります。

nicomimi -にこみみ- ニコニコ動画mp3変換サービス
http://www.nicomimi.net/

ほかにもブラウザの拡張機能を利用するという手もあります。

国内の拡張機能でそれなりに有名なのは、ニコチューブゲッダンだと思います。

これはブラウザであるＣｈｒｏｍｉｕｍ/Chromeの拡張機能でして、ニコニコ動画とYoutubeのDownloadが見ているそのページにダウンロードボタンが埋め込まれる形でダウンロードできる拡張機能です。

そこからUbuntu上で動画から音声を抜き出していくという手もありますし、拡張機能自体でYoutubeから直接MP3で落としてくるブラウザの拡張機能があるようです。

こういったものはFirefoxの拡張機能に多いようです。

拡張機能を利用したこういったことはブラウザ上でできることですのでOSは関係ありませんので試されてはいかがでしょうか。

まとめますと・・・・

ニコニコ動画の音声→にこさうんど(ブラウザ用のブックマークレットが用意されています。動画によっては音質が悪いものが混じりますが手軽です。)
ニコニコ動画の動画→ダウンロードできるようなウェブサービス、Firefoxの拡張機能。
Youtubeの音声→Firefoxの拡張機能(ダウンロードできるウェブサービスに飛ばすものと、Firefoxで直接MP3を落としてくるものの２種類が存在するようです)。
Youtubeの動画→ニコチューブゲッダン(Chrome拡張機能。ダウンロードするときに画質も選べます。),Firefoxの各種拡張機能。

もしくは動画ダウンロード後Ubuntuのマルチメディア系のソフトウェア群で音声だけ抜き出し→サウンド変換でMP3へ

でできると思います。

本来ならニコニコ動画の音声と動画までニコチューブゲッダンでダウンロードできていたようなのですが、最近サービスが停止しており、Youtubeの動画のダウンロードだけ残っているような形になっています。

くれぐれも著作権関係にだけは気をつけてください。

今、wineで動かしたCravingExplorerからダウンロードしたMP3を聞きながら書き込んでいます。

普通の方法では動かないので困っていたのですが、wineをインストール後winetricksを使いIE7とWindows用のFlashをインストール、その後CravingExplorerをインストールすることでダウンロード→MP3変換まで成功しました。

Ubuntu10.10です。wineは1.2.1-0ubuntu1 (wine1.2)を利用しています。

自分の環境ではうまく行きましたが、自己責任でお願いします。