How to use WITH RECURSIVE with values in an array?
Evidently, the answer required me to step away from it for a little bit.

Here's the query that solved my problem:

WITH RECURSIVE descendents AS (
  SELECT parent,unnest(children) AS child 
  FROM offspring o 
  WHERE parent='aaaaaaaa-8865-4b40-a482-78fc8a27d1bb' 
    UNION ALL
  SELECT o.parent,unnest(o.children) AS child 
  FROM offspring o, descendents d 
  WHERE o.parent = d.child) 
SELECT distinct(child) FROM descendents;


SQL Fiddle