TL;DR
Here's a version where you don't need a human to read a value and type it out themselves.
CREATE SEQUENCE foo_a_seq OWNED BY foo.a;
SELECT setval('foo_a_seq', coalesce(max(a), 0) + 1, false) FROM foo;
ALTER TABLE foo ALTER COLUMN a SET DEFAULT nextval('foo_a_seq'); 
Another option would be to employ the reusable Function shared at the end of this answer.
A non-interactive solution
Just adding to the other two answers, for those of us who need to have these Sequences created by a non-interactive script, while patching a live-ish DB for instance.
That is, when you don't wanna SELECT the value manually and type it yourself into a subsequent CREATE statement.
In short, you can not do:
CREATE SEQUENCE foo_a_seq
    START WITH ( SELECT max(a) + 1 FROM foo );
... since the START [WITH] clause in CREATE SEQUENCE expects a value, not a subquery.
Note: As a rule of thumb, that applies to all non-CRUD (i.e.: anything other than INSERT, SELECT, UPDATE, DELETE) statements in pgSQL AFAIK.
However, setval() does! Thus, the following is absolutely fine:
SELECT setval('foo_a_seq', max(a)) FROM foo;
If there's no data and you don't (want to) know about it, use coalesce() to set the default value:
SELECT setval('foo_a_seq', coalesce(max(a), 0)) FROM foo;
--                         ^      ^         ^
--                       defaults to:       0
However, having the current sequence value set to 0 is clumsy, if not illegal.
Using the three-parameter form of setval would be more appropriate:
--                                             vvv
SELECT setval('foo_a_seq', coalesce(max(a), 0) + 1, false) FROM foo;
--                                                  ^   ^
--                                                is_called
Setting the optional third parameter of setval to false will prevent the next nextval from advancing the sequence before returning a value, and thus:
the next nextval will return exactly the specified value, and sequence advancement commences with the following nextval.
— from this entry in the documentation
On an unrelated note, you also can specify the column owning the Sequence directly with CREATE, you don't have to alter it later:
CREATE SEQUENCE foo_a_seq OWNED BY foo.a;
In summary:
CREATE SEQUENCE foo_a_seq OWNED BY foo.a;
SELECT setval('foo_a_seq', coalesce(max(a), 0) + 1, false) FROM foo;
ALTER TABLE foo ALTER COLUMN a SET DEFAULT nextval('foo_a_seq'); 
Using a Function
Alternatively, if you're planning on doing this for multiple columns, you could opt for using an actual Function.
CREATE OR REPLACE FUNCTION make_into_serial(table_name TEXT, column_name TEXT) RETURNS INTEGER AS $$
DECLARE
    start_with INTEGER;
    sequence_name TEXT;
BEGIN
    sequence_name := table_name || '_' || column_name || '_seq';
    EXECUTE 'SELECT coalesce(max(' || column_name || '), 0) + 1 FROM ' || table_name
            INTO start_with;
    EXECUTE 'CREATE SEQUENCE ' || sequence_name ||
            ' START WITH ' || start_with ||
            ' OWNED BY ' || table_name || '.' || column_name;
    EXECUTE 'ALTER TABLE ' || table_name || ' ALTER COLUMN ' || column_name ||
            ' SET DEFAULT nextVal(''' || sequence_name || ''')';
    RETURN start_with;
END;
$$ LANGUAGE plpgsql VOLATILE;
Use it like so:
INSERT INTO foo (data) VALUES ('asdf');
-- ERROR: null value in column "a" violates not-null constraint
SELECT make_into_serial('foo', 'a');
INSERT INTO foo (data) VALUES ('asdf');
-- OK: 1 row(s) affected