I found this very helpful. It worked great with Django 1.3, PostgreSQL 8.3 in 2011/06:

And the penultimate step (filling in the primary key in existing rows) took around half a minute for almost 200,000 records on a not-particularly well-endowed laptop.

Summary:

CREATE SEQUENCE rcvh7_id_seq;
ALTER TABLE rcvh7 ADD id INT UNIQUE;
ALTER TABLE rcvh7 ALTER COLUMN id SET DEFAULT NEXTVAL('rcvh7_id_seq');
UPDATE rcvh7 SET id = NEXTVAL('rcvh7_id_seq');
ALTER TABLE rcvh7 ALTER COLUMN id SET NOT NULL;