How to (optimally) get random sample of (a.id, b.id) pairs from two tables (a, b)?
The best solution depends on the exact definition of your setup. For the example setup it's trivial:

Serial integer columns without gaps.


SELECT DISTINCT
           1 + trunc(random() * 100)::int AS a_id
     , 10001 + trunc(random() * 100)::int AS b_id
FROM   generate_series(1, 1100) g  -- enough excess to make up for possible dupes
LIMIT  1000;  -- only take 1000

The only interesting question: how to fold dupes efficiently. The solution: let Postgres decide. Simply use DISTINCT.
We don't even need to involve the tables at all. Super fast.
Note that random() generates (per documentation):

random value in the range 0.0 &lt;= x &lt; 1.0

Hence 1 + trunc(random() * 100)::int to cover ID numbers between 1 and 100 exactly.
Actual setup?
You need be be more specific about your actual setup. Let's assume there is at least a payload column in each of your tables, not just ID columns.
CREATE TABLE a(a_id integer PRIMARY KEY, a text);
CREATE TABLE b(b_id integer PRIMARY KEY, b text);

INSERT INTO a(a_id, a)
SELECT g, 't' || g FROM generate_series(    1,   100) g;
INSERT INTO b(b_id, b)
SELECT g, 't' || g FROM generate_series(10001, 10100) g;

Query:
SELECT a.a_id, a.a, b.b_id, b.b
FROM  (
    SELECT DISTINCT
               1 + trunc(random() * 100)::int AS a_id  -- cover *whole* key space
         , 10001 + trunc(random() * 100)::int AS b_id  -- maybe add reserve for new rows
    FROM   generate_series(1, 1100) g
    LIMIT  1000
    ) ra
JOIN   a USING (a_id)
JOIN   b USING (b_id);

Truly random, very fast and almost independent of the actual table size.
All you need is indexes on a(a_id) and b(b_id). Or possibly multicolumn indexes to allow index-only scans.

The solution also works for a few gaps from skipped nextval() calls, as long as there are not much more gaps than islands, it's still very cheap to generate enough combinations to cover losses by gaps. (Much cheaper than working with a Cartesian product of big tables or sorting whole big tables with ORDER BY random() anyway.) Just be sure to generate enough combinations.
SELECT a.a_id, a.a, b.b_id, b.b
FROM  (
    SELECT DISTINCT
               1 + trunc(random() * 100)::int AS a_id
         , 10001 + trunc(random() * 100)::int AS b_id
    FROM   generate_series(1, 1100) g  -- enough to cover dupes *and* gaps
    ) ra
JOIN   a USING (a_id)
JOIN   b USING (b_id)
LIMIT  1000;  -- LIMIT moves to outer query to cover gaps

With more than a few gaps, start with a number of combinations that's enough 95 % of the time and add a recursive step to add more rows if you should fall short. There is a recipe for this solution (for a single table) in the related answer. Also more explanation and variations:

Best way to select random rows PostgreSQL