Oh, my gosh. I feel so honored to have my banner exchange mentioned. Thanks shaunak! You may also want to try some of the click exchange programs. I don't really endorse them (you'll note I include no referral urls), but it is said if your website is webmaster related you can expect a small amount of benefit from them. I dare say most of your efforts will produce a very small result. It is the combination of all these small results that produce eventual success. Here are the links if you want to try some.
http://www.looking4traffic.com
http://www.clickthru.com
http://www.iloveclicks.com
If you decide to try these programs (there are tons more, I'm just most familiar with these) it is suggested you open more than 1 at a time (3 would be nice). That way you are earning 3 credits at a time. However, you should note that everyone else is most likely doing the same thing. (Translation: They have 3 windows open. They aren't even looking at the websites really. It's a gamble.)
Of course, you'll want to get listed in the search engines. I've heard it is best to try and get into
http://www.dmoz.org first, since Yahoo!, Google, and many of the other major search engines actually take results from DMOZ to propagate their listings. You should try to get listed in search engines and trade links with similar websites as these produce results without further effort on your part.
Of course, I humbly (lol) suggest you join my banner exchange. It's free and it offers one of the highest exchange ratios available. The best thing about banner exchanges is they work off the efforts you have already done. It is similar to purchasing banner impressions, except you earn them. In my past experiences, banner exchanges have been beneficial, but to a small degree. I am trying to change that by offering higher ratios and forcing members to place the ad code in a more prominent position.