Complex constraint across all data in a table
Tested with Postgres 9.1 &amp; 9.2. Most of it should work for 8.4 as well.

Simple case

Without intermediate states violating the constraint over the course of a single transaction, a partial UNIQUE index on a constant value does the job. Given this test case:

CREATE TEMP TABLE jobs(jobs_id int primary key, status text);
INSERT INTO jobs (jobs_id, status)
VALUES (1, 'A'), (2, 'B'), (3, 'C'), (4, 'G');


Use this index:

CREATE UNIQUE INDEX jobs_status_uni_idx ON jobs ((TRUE))
WHERE status in ('P', 'G');


Note the additional set of parenthesis around the value TRUE.

Test (one line at a time):

INSERT INTO jobs (jobs_id, status) VALUES (5, 'G'); -- fails
INSERT INTO jobs (jobs_id, status) VALUES (5, 'P'); -- fails

DELETE FROM jobs WHERE status = 'G';

INSERT INTO jobs (jobs_id, status) VALUES (5, 'P'); -- succeeds
INSERT INTO jobs (jobs_id, status) VALUES (6, 'G'); -- fails


SQL Fiddle.

Related answer with more explanation:
PostgreSQL multi-column unique constraint and NULL values

Advanced case with DEFERRED constraint


  ideally this check would happen on commit


A partial unique index cannot be deferred and is always checked immediately. Therefore, continuing the example from above, this would fail:

BEGIN;
INSERT INTO jobs (jobs_id, status) VALUES (6, 'G');  -- fails immediately!
DELETE FROM jobs WHERE status = 'P';
COMMIT;


Example is with explicit transaction handling. Your client may have automatic transaction handling (autocommit on or off).

If you need this to work, you need a DEFERRABLE constraint that is INITIALLY DEFERRED or SET CONSTRAINTS ALL | name  DEFERRED within the transaction.

I quote the manual here


  Non-deferred Uniqueness Constraints
  
  When a UNIQUE or PRIMARY KEY constraint is not deferrable, PostgreSQL
  checks for uniqueness immediately whenever a row is inserted or
  modified. The SQL standard says that uniqueness should be enforced
  only at the end of the statement; this makes a difference when, for
  example, a single command updates multiple key values. To obtain
  standard-compliant behavior, declare the constraint as DEFERRABLE but
  not deferred (i.e., INITIALLY IMMEDIATE). Be aware that this can be
  significantly slower than immediate uniqueness checking.


More gory details about Index Uniqueness Checks in the manual.

However, a UNIQUE CONSTRAINT can only be defined for columns, not for expressions.
Add a redundant column for this purpose and keep it current with triggers. Like this:

ALTER TABLE jobs ADD COLUMN status_uni boolean;
UPDATE jobs set status_uni = TRUE WHERE status in ('P', 'G');  -- rest stays NULL


ALTER TABLE jobs ADD CONSTRAINT jobs_status_uni
UNIQUE(status_uni) DEFERRABLE INITIALLY DEFERRED;

The additional column is cheap, since it is filled with NULLs, an existing NULL bitmap should normally swallow it without the need for additional physical disk space.
NULL values do not violate a unique constraint per definition.

Create triggers to keep the column current at all times:

CREATE OR REPLACE FUNCTION trg_jobs_status()
  RETURNS trigger AS
$func$
BEGIN
NEW.status_uni = (NEW.status IN ('G', 'P') OR NULL);
RETURN NEW;
END
$func$  LANGUAGE plpgsql;


For all inserts:

CREATE TRIGGER insbef
BEFORE INSERT ON jobs
FOR EACH ROW EXECUTE PROCEDURE trg_jobs_status();


To optimize, only for relevant updates:

CREATE TRIGGER upbef
BEFORE UPDATE OF status, status_uni ON jobs
FOR EACH ROW EXECUTE PROCEDURE trg_jobs_status();


Test

Now your transactions go through, as long as the state is consistent at the end:

BEGIN;
-- SET CONSTRAINTS jobs_status_uni IMMEDIATE;  -- only for INITIALLY IMMEDIATE
INSERT INTO jobs (jobs_id, status) VALUES (6, 'G');  -- check deferred
DELETE FROM jobs WHERE status = 'P';
COMMIT;  -- succeeds!


SQL Fiddle.