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.