Originally Posted by Saint_23

I used to work for a company who specialise in exactly this.

My advice - dont pay any of these companies to do it for you.

Start by getting the head metatags sorted. Namely the description and keywords.
Then you can submit to direct to most major search engines for inclusion.
I haven't done it for a while, but I'll see if i can dig up some links.