Using the daemon and not a 3rd party pinging service, what is the best way to get notified of new payments? Do we need to constantly poll the server?
Bitcoin New transactions can be discovered by polling using the listsinceblock API command with the Bitcoin.org client.
Beginning with v0.8.2 of the Bitcoin-Qt/bitcoind client is -walletnotify option that can run a process when a transaction that affects the wallet is seen.
The BitsOfProof supernode will offer this as well I believe.
[Update: Thanks to Pelle's answer to a related question,
You can do this using BitcoinJ by implementing the PeerEventListener interface.
The OnTransaction will be called every time a new Transaction is broadcast out and received from a Peer ]