Yes, it's true that the more sites that link to you the better you can rank with the major player (i.e. Google) although I'm not sure as to the ranking method of the other big two - Yahoo! and MSN.
Google uses its PR (Page Ranking) to rate a site to other users. The PR is raised by links to the site in addition to numerous other little factors such as contextual links, keywords, headers and page titles, etc. If you want to get link exchanges going then those sites with a higher PR carry most weight. The exact ratio is not known but, as an example, a site with a PR of 4 linking to you could carry the equivalent of 50 links from a batch of sites with a PR of 3.
Try to find link exchanges with sites holding a PR of 4 and above. They'll help you rise in Google's search results. Also, link with pages of similar content - there's less effect in a computer site linking to a military history site than there would be a computer site exchanging links with a software site.
Take heed of SEO (Search Engine Optimisation) though - there's other things that will help you move up the search engines' results. And be patient - it takes time.
Link exchanges are generally a waste of time, IMO.
The amount of effort is not worth the marginal benefit.
Pursue one way inbound links.
It's not simply about quantity, quality of inbound links is more important.
Ignore the PR meter on your toolbar, it has not been updated in months.
Pursue link partners that rank highly for your search queries. Make sure their pages are constantly changing, and that they do not oversaturate their pages with links.