How do I install pgcrypto in PostgreSQL 8.4?
PostgreSQL 9.1+

Note that I'm working on Ubuntu 12.04, which uses postgresql 9.1.

There, I needed to:

sudo apt-get install postgresql-contrib


And then in my database:

postgres@ztrustee:~$ psql test
psql (9.1.3)
Type "help" for help.
test=# CREATE EXTENSION pgcrypto;
CREATE EXTENSION


And now I can use pgcrypto functionality, gen_random_bytes():

test=# create table test ( 
  id 
    text 
    not null 
    default encode( gen_random_bytes( 32 ), 'hex' ) 
    primary key, 
  value 
    text 
); 
NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "test_pkey" for table "test"
CREATE TABLE
test=# \d test
                            Table "public.test"
 Column | Type |                         Modifiers                          
--------+------+------------------------------------------------------------
 id     | text | not null default encode(gen_random_bytes(32), 'hex'::text)
 value  | text | 
Indexes:
    "test_pkey" PRIMARY KEY, btree (id)

test=# insert into test (value) VALUES ('scoobydoo');
INSERT 0 1
test=# select * from test;
                                id                                |   value   
------------------------------------------------------------------+-----------
 76dd5bd0120d3df797f932fbcb4f8aa5088e215ee2b920dddbff59c8595fbac7 | scoobydoo