SEM (Marketing) involves all the points you mentioned and
SEO is where you need to begin...
optimize your website
1. start with a good title and meta tags on all pages
2. provide good keyword rich content on your pages
3. clean up your HTML, Validate it
4. add a sitemap and/or good text links to your pages
5. use a Keyword density analyser (
http://www.searchengineworld.com/cgi-bin/kwda.cgi)
6. study opposition websites and "steal" ideas
7. there are more points, maybe some1 could assist
when you have optimized your site, then move on to your other points
1. Start a linking campaign - reciprocal links
2. Add your site to directories
3. don't worry about Search engines, if your link is add by good sites, SE's will find you
4. i am not an expert on Paid linking or buying links and have never paid to be listed, yet.
5. try Google Adwords
I am not expert, but this is more or less the route i followed and we get good results, especially from searches via Google without paying for links, paying for inclusion or even Adwords.
The key, the way i see it, is to (1) optimize your site and then (2) build quality links