It depends on what you're looking for in a handheld system.
The PSP is rather lacking in fun and well made games, so it really falls short for most people that would use it -just- to game. The only good personal testimony I've heard about it is from an online friend who actually puts other features of the PSP to good use, such as the MP3 player and the portable movies. Game wise, the PSP offers more mature themed games, mostly in the shooter department... though a lot of them don't handle very well. There's also a pretty big selection of racing games.
The Nintendo DS offers a huge variety of puzzle games, which is probably what it does best. Most DS games are geared more for short burst play... as in you can sit there for maybe 10-20 minutes before turning it off again for a while. It does support gameboy advanced games, which includes a lot of classic SNES titles and remakes, which is great for the sidescrolling platform lover. Metroid Zero Mission (remake of the original metroid), several good castlevania games, Drill Dozer, and most of the 2D mario games through the ages are playable through Advanced or DS... on the DS. Many of the lighthearted and even 'kiddy' classified games can be found on the DS, which is great if you have youngins.
Both systems offer online play, but few games actually support it. If you have a wireless router in your home, usually the games can be configured to run through it. Both also offer short ranged wireless connections for head to head and coop play (based on the games) in the same spirit that was introduced with the original gameboy release, just without the annoying link cords.
The deciding factor should really come down to which system offers more games you'd like own, since they only -really- overlap in the puzzle area, but other wise sport completely different styles.