Hey Hafi,
The list of packages that Pill gave you should work on Edgy. How you install a Debian package is a bit different than adding a .dll file in Windows.
You can do two things, either add a line like the one below to the file in /etc/apt/sources.list
deb ftp://ftp.fi.debian.org/debian/ stable main testing
That example is for the Finland mirror. You will already have a line like it in your sources.list file. The crucial part is to have "testing" in there, which is where the Gem packages live.
Then just say
sudo apt-get install Gem
and it should do everything for you.
ALternatively, download the packages from the links above, which are .deb packages, and say something like
sudo dpkg -i Gem.deb
This method may cause you dependency problems though so be warned.
An even better way is to do some reseach on the very good Ubuntu forums about installing "testing" packages. If you do everything through the proper package manager it's bound to be less painful in the end.