I looked in the "friends" section of the PSN website, and I couldn't find any way to search for other friends to add.
Can this be done anywhere online or can it be only done through the console system?
The ability to add friends via the website is a popular feature request (a quick Google search will turn up dozens of threads going back years asking for it), but it has never been added.
So as of now, you can only do it through the PlayStation 3, PlayStation Vita, or PlayStation 4 (oddly, you can't even add friends on the PSP).
Very old question, but in case someone is googling this, now you can do it:
https://my.playstation.com/ and navigate to "Friends". From there you can now search, add friends, manage requests and everything else you could only do in the app before.