Plain INSERT

INSERT INTO bar (description, foo_id)
SELECT val.description, f.id
FROM  (
   VALUES
      (text 'testing', text 'blue')  -- explicit type declaration; see below
    , ('another row', 'red' )
    , ('new row1'   , 'purple')      -- purple does not exist in foo, yet
    , ('new row2'   , 'purple')
   ) val (description, type)
LEFT   JOIN foo f USING (type);

• The use of a LEFT [OUTER] JOIN instead of [INNER] JOIN means that rows from val aren't dropped when no match is found in foo. Instead, NULL is entered for foo_id.

• The VALUES expression in the subquery does the same as @ypercube's CTE. Common Table Expressions offer additional features and are easier to read in big queries, but they also pose as optimization barriers. So subqueries are typically a bit faster when none of the above is needed.

• id as column name is a wide-spread anti-pattern. Should be foo_id and bar_id or anything descriptive. When joining a bunch of tables, you end up with multiple columns all named id ...

• Consider plain text or varchar instead of varchar(n). If you really need to impose a length restriction, add a CHECK constraint:

  • Should I add an arbitrary length limit to VARCHAR columns?

• You may need to add explicit type casts. Since the VALUES expression is not directly attached to a table (like in INSERT ... VALUES ...), types cannot be derived and default data types are used without explicit type declaration, which may not work in all cases. It's enough to do it in the first row, the rest will fall in line.

INSERT missing FK rows at the same time

If you want to create non-existent entries in foo on the fly, in a single SQL statement, CTEs are instrumental:

WITH sel AS (
   SELECT val.description, val.type, f.id AS foo_id
   FROM  (
      VALUES
         (text 'testing', text 'blue')
       , ('another row', 'red'   )
       , ('new row1'   , 'purple')
       , ('new row2'   , 'purple')
      ) val (description, type)
   LEFT   JOIN foo f USING (type)
   )
, ins AS ( 
   INSERT INTO foo (type)
   SELECT DISTINCT type FROM sel WHERE foo_id IS NULL
   RETURNING id AS foo_id, type
   )
INSERT INTO bar (description, foo_id)
SELECT sel.description, COALESCE(sel.foo_id, ins.foo_id)
FROM   sel
LEFT   JOIN ins USING (type);

Note the two new dummy rows to insert. Both are purple, which does not exist in foo, yet. Two rows to illustrate the need for DISTINCT in the first INSERT statement.

Step-by-step explanation

1. The 1st CTE sel provides multiples rows of input data. The subquery val with the VALUES expression can be replaced with a table or subquery as source. Immediately LEFT JOIN to foo to append the foo_id for pre-existing type rows. All other rows get foo_id IS NULL this way.

2. The 2nd CTE ins inserts distinct new types (foo_id IS NULL) into foo, and returns the newly generated foo_id - together with the type to join back to insert rows.

3. The final outer INSERT can now insert a foo.id for every row: either the type pre-existed, or it was inserted in step 2.

Strictly speaking, both inserts happen "in parallel", but since this is a single statement, default FOREIGN KEY constraints will not complain. Referential integrity is enforced at the end of the statement by default.

SQL Fiddle for Postgres 9.3. (Works the same in 9.1.)

There is a tiny race condition if you run multiple of these queries concurrently. Read more under related questions here and here and here. Really only happens under heavy concurrent load, if ever. In comparison to caching solutions like advertised in another answer, the chance is super-tiny.

Function for repeated use

For repeated use I would create an SQL function that takes an array of records as parameter and use unnest(param) in place of the VALUES expression.

Or, if the syntax for arrays of records is too messy for you, use a comma-separated string as parameter _param. For instance of the form:

'description1,type1;description2,type2;description3,type3'

Then use this to replace the VALUES expression in above statement:

SELECT split_part(x, ',', 1) AS description
       split_part(x, ',', 2) AS type
FROM unnest(string_to_array(_param, ';')) x;

Function with UPSERT in Postgres 9.5

Create a custom row type for parameter passing. We could do without it, but it's simpler:

CREATE TYPE foobar AS (description text, type text);

Function:

CREATE OR REPLACE FUNCTION f_insert_foobar(VARIADIC _val foobar[])
  RETURNS void AS
$func$
   WITH val AS (SELECT * FROM unnest(_val))    -- well-known row type
   ,    ins AS ( 
      INSERT INTO foo AS f (type)
      SELECT DISTINCT v.type                   -- DISTINCT!
      FROM   val v
      ON     CONFLICT(type) DO UPDATE          -- type already exists
      SET    type = excluded.type WHERE FALSE  -- never executed, but lock rows
      RETURNING f.type, f.id
      )
   INSERT INTO bar AS b (description, foo_id)
   SELECT v.description, COALESCE(f.id, i.id)  -- assuming most types pre-exist
   FROM        val v
   LEFT   JOIN foo f USING (type)              -- already existed
   LEFT   JOIN ins i USING (type)              -- newly inserted
   ON     CONFLICT (description) DO UPDATE     -- description already exists
   SET    foo_id = excluded.foo_id             -- real UPSERT this time
   WHERE  b.foo_id IS DISTINCT FROM excluded.foo_id  -- only if actually changed
$func$  LANGUAGE sql;

Call:

SELECT f_insert_foobar(
     '(testing,blue)'
   , '(another row,red)'
   , '(new row1,purple)'
   , '(new row2,purple)'
   , '("with,comma",green)'  -- added to demonstrate row syntax
   );

Fast and rock-solid for environments with concurrent transactions.

In addition to the queries above, this ...

• ... applies SELECT or INSERT on foo: Any type that doesn't exist in the FK table, yet, is inserted. Assuming most types pre-exist. To be absolutely sure and rule out race conditions, existing rows we need are locked (so that concurrent transactions cannot interfere). If that's too paranoid for your case you can replace:

    ON     CONFLICT(type) DO UPDATE          -- type already exists
    SET    type = excluded.type WHERE FALSE  -- never executed, but lock rows
  

  with

    ON     CONFLICT(type) DO NOTHING
  

• ... applies INSERT or UPDATE (true "UPSERT") on bar: If the description already exists its type is updated:

    ON     CONFLICT (description) DO UPDATE     -- description already exists
    SET    foo_id = excluded.foo_id             -- real UPSERT this time
    WHERE  b.foo_id IS DISTINCT FROM excluded.foo_id  -- only if actually changed
  

  But only if type actually changes:

  • How do I (or can I) SELECT DISTINCT on multiple columns?

• ... passes values as well known row types with a VARIADIC parameter. Note the default maximum of 100 parameters! Compare:

  • Select rows such that names match elements of input array for pgsql function

  There are many other ways to pass multiple rows ...

Related:

• How to include excluded rows in RETURNING from INSERT ... ON CONFLICT

Lookup. You basically need the foo id's to insert them into bar.

Not postgres specific, btw. (and you did not tag it like that) - this is generally how SQL works. No shortcuts here.

Application wise, though, you may have a cache of foo items in memory. My tables often have up to 3 unique fields:

• Id (integer or something) that is the table level primary key.
• Identifier, which is a GUID that is used as stable ID application level wise (and may be exposed to the customer in URL's etc.)
• Code - a string that may be there and has to be unique if it is there (sql server: filtered unique index on not null). That is a customer set identifier.

Example:

• Account (in a trading application) -> Id is a int used for foreign keys. -> Identifier is a Guid and used in the web portals etc. - always accepted. -> Code is manually set. Rule: once set it does not change.

Obviously when you want to link something to an account - you first must, technically, get the Id - but given both Identifier and Code never change once they are there, a positive cache in memory kan stop most lookups from hitting the database.