Submit to the search engines. Keep track of what one's have accepted and listed you so you don't agrivate them by doing it after your listed.
Exchange links. Find simular sites such as yours and write them a formal letter offering to exchange links. This can be benificial to both sites in question.
While surfing the net keep an eye out for "free for all" link pages. Add your site every opertunity you get.
Study up on <meta> tags. Depending on the search engine this can be a very big part of listing. I have a post in the "how do I..." forum covering how to add the "keywords" and "description" tags to your forum pages.
Look at simular, well ranked sites. See what they are using for their meta tags. If at all possible, try and use some well known words that pertain to your site but you haven't seen in your "competitor" sites. You'll rank high when users hit them words since the other sites do not have them.
Don't fill your pages full of hidden keywords and whatnot. Search engines are smarter than they used to be and this may very well get your site overlooked on purpose.
Banner exchanges. From my own experiences these help a little. Your main traffic will come from people using search engines to find sites like yours though.
Register your site with the various "open directory" groups out there. This isn't a search engine so much as it's a yellow pages for the internet. You may be added quicker to these directories than the search engines.
And finally, it's a time thing. Consistant content, friendly users and patience will win out in the long run.
Good Luck