According to what I can gather from the mailing list, to add a friend from another seed you need to add the seed's address, as in 'user@server.com'
In the future, the goal would be to implement:
Web services interface to enable seed to seed communication (federation)
DHT (distributed hash table), to enable seeds to share their list of known seeds with each other, so a new seed would only need to add a couple of other existing seeds to receive new entries for its list.
If you are on different servers, you need to use your full Diaspora IDs. Type something like nameofyourfriend@joindiaspora.com into the search field at the top, and it should find his account after a while. (Or he can do the same with your full ID.)
Another option (if you cannot find him for some reason): On the right side there is a link titled Share this link via email, blog, or favorite social network!. Just send him this link and he should be able to connect to you by visiting it.
Best Answer
I don't know about Diaspora, but you can create one with Ning.