Essentially the answer (for PostgreSQL 9.1 and up) is that you will need to run these SQL statements against the Rails database. Probably the easiest way to do this is to write a migration using the execute method. Postgresql user of your rails app should be superuser to create these extensions

class InstallSomeContribPackages < ActiveRecord::Migration
  def up
    execute "CREATE EXTENSION IF NOT EXISTS pg_trgm;"
    execute "CREATE EXTENSION IF NOT EXISTS fuzzystrmatch;"
  end
  def down
    execute "DROP EXTENSION IF EXISTS pg_trgm;"
    execute "DROP EXTENSION IF EXISTS fuzzystrmatch;"
  end
end

If this fails, then you will need to install the contrib packages through whichever mechanism is best for your OS. In Mac OS X, I use Homebrew to install PostgreSQL, which compiles and installs all the contrib packages by default. Ubuntu appears to have a package called postgresql-contrib.

Note that the contrib packages need to be present on the server running the database, which might be different than the server running the application. Heroku supports a few contrib packages, but I don't know the details on how to set them up there.

You will need to run them for each environment.

If you're using Rails 3.1 and lower, you'll need to change the schema format in your config/application.rb file (as explained in the migrations guide):

config.active_record.schema_format = :sql

For Rails 4 and higher, this is not required as the following will be added to the schema.rb automatically:

# These are extensions that must be enabled in order to support this database
enable_extension "plpgsql"
enable_extension "pg_trgm"