I've seen this happen when the user's home directory isn't local, but on an NFS automount on the network. If your home directory isn't already mounted when sshd goes to look for your ~/.ssh/authorized_keys, it won't be able to access it in time, so public-key-based authentication will fail.
ssh-agent is the piece that you want to get working, as it does exactly what you're asking about. The agent runs as a daemon, and when you "add" a private key to it, it remembers that key and automatically provides it to the remote sshd during the initial connection. (ssh-add is simply the command you run to manually add a private key to ssh-agent).
In OS X, as of Leopard, you shouldn't ever have to run ssh-agent or ssh-add manually. It should "just happen" when you attempt to connect to a server. Once per key, it will prompt you with a UI password dialog, which (among other things) will allow you to automatically add the key to the ssh-agent so you never get prompted again.
This is handled by having a launchd configuration that listens for connections on the $SSH_AUTH_SOCK socket, and automatically launches ssh-agent when it first needs to; after that, ssh-agent prompts you for credentials only when it needs to open a new key.
If that's not working, make sure you have the correct launchd configuration file present:
/System/Library/LaunchAgents/org.openbsd.ssh-agent.plist
If it's still not working for you for some reason, here's the "old" way of getting things running by hand:
http://timesinker.blogspot.com/2007/08/getting-ssh-agent-going-on-mac-osx.html
There is also this application, which I have stopped using since Leopard came out but basically did the same thing in previous versions of Mac OS X:
http://www.sshkeychain.org/
Best Answer
After some more googling I finally understood what this answer means:
https://security.stackexchange.com/a/9635
What needs to be done beforehand for this answer to work out is:
After that, I did:
One would think there's an easier way to do this. Spent solid 2 hours to figure this out...