Optimizing concurrent updates in Postgres

There is no ORDER BY in an SQL UPDATE command. Postgres updates rows in arbitrary order:
UPDATE with ORDER BY

To avoid deadlocks with absolute certainty, you could run your statements in serializable transaction isolation. But that's more expensive and you need to prepare to repeat commands on serialization failure.

Your best course of action is probably to lock explicitly with SELECT ... ORDER BY ... FOR UPDATE in a subquery or a standalone SELECT in a transaction - in default "read committed" isolation level. Quoting Tom Lane on pgsql-general:

Should be all right --- the FOR UPDATE locking is always the last step in the SELECT pipeline.

This should do the job:

BEGIN;

SELECT 1
FROM   foo 
WHERE  baz = 1234
ORDER  BY bar
FOR    UPDATE;

UPDATE foo
SET    bar = bar + 1
WHERE  baz = 1234;

COMMIT;

A multicolumn index on (baz, bar) might be perfect for performance. But since bar is obviously updated a lot, a single-column index on just (baz) might be even better. Depends on a couple of factors. How many rows per baz? Are HOT updates possible without the multicolumn index? ...

If baz is updated concurrently, there is still a corner case chance for conflicts:

It is possible for a SELECT command running at the READ COMMITTED transaction isolation level and using ORDER BY and a locking clause to return rows out of order. ...

More in the manual here.

Also, if you should have a unique constraint on bar, consider a DEFERRABLE constraint.
The manual on the matter.
Related answer:
Constraint defined DEFERRABLE INITIALLY IMMEDIATE is still DEFERRED?