When downloading the blockchain for the first time using bitcoind, how do I know when it's done? I'm using bitcoind on Ubuntu, headless. So there's no GUI to tell me when it's done.

So how do I know?
Run bitcoind getinfo in your shell of choice and compare the block count, listed after "blocks", to the block count listed here. If the two numbers are the same, your client is up to date.