Run the following command from your terminal:

sudo apt-get purge ruby

Usually works well for me.

(caution: this can delete essential system files related to GRUB and other components)

If you're using Ubuntu Packages run sudo apt-get purge <packages>

So that should be something like:

sudo apt-get purge ruby rubygems

From the apt-get man page:

  purge
      purge is identical to remove except that packages are removed and purged (any configuration files are deleted too).

If your package manager installed Ruby to begin with, then something on your system needs it.

The easiest way to find out what needs it is to test an attempt to remove the package. For instance:

# yum remove ruby
...
================================================================================
 Package         Arch      Version                Repository               Size
================================================================================
Removing:
 ruby            x86_64    1.8.7.352-12.el6_4     @updates                1.8 M
Removing for dependencies:
 facter          x86_64    1:1.7.3-1.el6          @puppetlabs-products    235 k
 hiera           noarch    1.2.1-1.el6            @puppetlabs-products     46 k
 puppet          noarch    3.3.0-1.el6            @puppetlabs-products    3.5 M
 ruby-irb        x86_64    1.8.7.352-12.el6_4     @updates                1.0 M
 ruby-rdoc       x86_64    1.8.7.352-12.el6_4     @updates                1.3 M
 ruby-rgen       noarch    0.6.5-1.el6            @puppetlabs-deps        315 k
 rubygem-json    x86_64    1.5.5-1.el6            @puppetlabs-deps        989 k
 rubygems        noarch    1.3.7-1.el6            @base                   711 k

Transaction Summary
================================================================================
Remove        9 Package(s)

Installed size: 9.9 M
Is this ok [y/N]: n
Exiting on user Command

So on my system, I see that it's needed by puppet. Since I actually need puppet, I will not remove ruby.

Similarly on Debian-based systems:

# apt-get remove ruby
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages were automatically installed and are no longer required:
  libshadow-ruby1.8 irb1.8 libaugeas0 rdoc libruby ruby1.8 rdoc1.8
  libaugeas-ruby1.8 puppet-common libruby1.8 libopenssl-ruby1.8
  libreadline-ruby1.8 libreadline5 libopenssl-ruby augeas-lenses
  libxmlrpc-ruby
Use 'apt-get autoremove' to remove them.
The following packages will be REMOVED:
  facter puppet ruby
0 upgraded, 0 newly installed, 3 to remove and 48 not upgraded.
After this operation, 983kB disk space will be freed.
Do you want to continue [Y/n]? n
Abort.

The package name is ruby1.9.1 but the software version is 1.9.3, so remove it running:

sudo apt-get remove ruby1.9.1 libruby1.9.1

Actually you can switch ruby versions with the following commands:

rvm install ruby_version

After the installation, we can list the available Ruby versions we have installed by typing:

rvm list

We can switch between the Ruby versions by typing:

rvm use ruby_version

We can use various Rails versions with each Ruby by creating gemsets and then installing Rails within those using the normal gem commands:

rvm gemset create gemset_name    # create a gemset
rvm ruby_version@gemset_name  # specify Ruby version and our new gemset
gem install rails -v rails_version   # install specific Rails version

Ubuntu...?

Use this to find out what executable you're running:

$ which ruby
/usr/bin/ruby

Use this to find out what it actually is:

$ readlink -f /usr/bin/ruby
/usr/bin/ruby1.8

Use this to find out what package it belongs to:

$ dpkg -S /usr/bin/ruby1.8
ruby1.8: /usr/bin/ruby1.8

Use this to uninstall that:

$ apt-get purge ruby1.8

Note: If you have installed Ruby using Version/Environment managers like RVM or Rbenv then this method is not gonna work because Rubies will be installed as scripts not packages.