They need to be online / logged into game at the time you look for them otherwise you'll unable to search / add them. And indeed you need to know and use the First and / or Last name of the character. Can't search using SE or PSN ID.