Let me give some suggestions on this
Without investing $
1) Create a perfect meta tag with some very good keywords relating to your website content.Dont fill in too much of keywords.To become a robot friendly website you are advised not to exceed more than 20 keywords.
2) Submit your site to all the major search engines manually.Dont use automated services as we cant say whether their submission is properly accepted by search engines or not.
3) Have a links page in your website and start exchanging links with other websites related to your industry.But never keep the page name as links.htm,links.php etc.This is because Google hates the word "link" or "links" and it will not crawl your links page then.Make sure you exchange links only with the website having a Google page rank more than 4.This is beause , if suppose we exchange links with site lesser than PR 4 our website's PR will also not cross 4.
To check a site's Google PR, either download the google toolbar from google.com or go to
http://www.rustybrick.com/pagerank-prediction.php
here you can check your current PR as well as your future PR.
Now ideas to invest $
Use Google Adwords program -
http://www.google.com/ads
Use Yahoo Overture sitematch -
http://www.overture.com
when you invest more and more in these programs, you website's popularity will also become more and more VERY SOON.
Hope i have given you some valuable suggestions.
Thanks