Personally I think search engines are your best bet. Make sure you are listed in dmoz, and if you have the cash, it might not hurt to get listed in Yahoo's directory... (although it makes me sick to my stomach that they charge $300 for that). Google will bump you higher in the search listings if you have a lot of other sites linking to yours, so try and get your site listed on other pertinent websites. You can also try Google's adwords program- you set how much you pay per click, and you set the daily maximum so you can set it as low as $0.05 per day... it really gives you a lot of control over your expenses and a lot of good exposure, IMHO.
I'm not sure what the nature of your site is, but you also want to make sure you have something "sticky" on there- so people will want to come back.. something that changes all the time. Providing a lot of good free info about a pertinent topic is also a good way to start getting your name out there... people will find you and refer you to others.
hth!
-Elizabeth