Has my 'cluster' operation succeeded? I ran this command:

cluster verbose address using address_locality_lookup;


And got this result:

INFO:  clustering "dba.address" using sequential scan and sort
INFO:  "address": found 0 removable, 29323623 nonremovable row versions in 1139047 pages
DETAIL:  0 dead row versions cannot be removed yet.
CPU 26.00s/8286.70u sec elapsed 8342.01 sec.
CLUSTER
Time: 9366585.421 ms


Does that indicate that clustering succeeded (ie all the rows are now in the order indicated by the address_locality_lookup index)?

What do 'removable', and 'nonremovable' indicate?
Yes, this means it succeeded.  Normally (when the client settings are like that), you get back an echo of the command executed, like CLUSTER in this case.

In newer PostgreSQL versions, CLUSTER and VACUUM FULL do mostly the same (in fact, to my knowledge, they share the same code), the only difference being the ordering by the former.  What you see are typical output of the different VACUUM commands, describing that there were no stale rows in your table. 

These can be either old versions of some existing rows, replaced by an UPDATE or deleted ones, which in both cases hadn't been removed by a previous VACUUM operation.  These are marked as 'removable', as opposed to some which may still be referenced by some open transactions.  When the transactions are closed, these will also be removable.