I was wondering whether there is way to make rhythmbox fetch or find metadata automatically online for all the songs in my library. Is such a task possible?
Unfortunately no, Rhythmbox doesn't support fetching of metadata not even through plugins. But there are better alternatives available in Ubuntu repositories. I would suggest EasyTAG
EasyTAG is an utility for viewing and editing tags for MP3, MP2, FLAC, Ogg Vorbis, Speex, MP4/AAC, MusePack, Monkey's Audio and WavPack files. Its simple and nice GTK2 interface makes tagging easier under GNU/Linux or Windows.
You can install it by running the following command in terminal.
sudo apt-get install easytag
or search for "easytag" in Software Center and install in from there.