I suggest to check what will come with the PDA as standard - it should always come with either a sync cradle or a sync cable - certainly you do not need to buy that item yourself.
If you are using your PDA very often (like me for business meeting in and out of the office) then I would suggest a good strong carry case.
You will also need to have a protective overlay to the screen - it will gather dust and can be scratched without protection.
Extra memory is not required, as during sync any data on your handheld should be backed up on your PC. However, you may want to put different type of files on a separate memory card (I put games and MP3 on mine) in order not to use up the PDA's memory.
If you need to input text to your PDA (say, for recording notes outwith the office) it is also beneficial to have a foldable fullsize qwerty keyboard.