"Do they have to be relevant sites?" - from the point of view of search engine optimization, no, not at present at least. However, in my opinion, things I see Google saying and doing lately suggest to me that relevance is going to become increasingly important. I also believe that a good part of the reason for linking to other sites is to help your own visitors so relevance in outgoing links is essential in my opinion - and that would apply to any one who agrees to link to you as well.
On the other hand, having a link somewhere to a single "partner site" in a different area is unlikely to hurt either of you.
As for the best way to build links, go to the search engines, type in relevant keywords, visit the sites that come up, and for those you like and would be willing to link to yourself, send an email to the contact saying something like the following:
Dear ---
I have just visited your website. Congratulations on creating an appealing and informative site!
I have placed a link to your site at http://www.mysite.com/page.html. Would you be willing to reciprocate? If so, here is the suggested link information for my site:
Thank you.
Now, I think it works better if you don't say that a reciprocal link is required but of course if you don't get a reciprocal link within some period of time I would imagine that most people would assume the link to them will be deleted...