While you can always use the dedicated apps for Facebook, Twitter, & LinkedIn to add new contacts SNEX is trying to simplify the process. The offer a handshake app that lets you connect two BlackBerrys over Bluetooth and add each other as contacts on your social networks. Sadly their iPhone app and BlackBerry app cannot work together over Bluetooth but they still work for manually adding contacts.
I have not had a chance to try out the app myself since the native apps work well for me but Stefano over @BBWorld.info found the app quite useful. Let us know if you give it a spin!