Back when the web was being carved into stone tablets, and web pages were delivered by donkey, finding information was a difficult task. Aside from the internet itself, when young, not actually having all that much information on everything, there were also a large number of competing engines and directories, and many people did not actually have much idea how to generate traffic from them.
Generally, at this stage, search engine results were pretty awful. Aside from the technology itself not being quite up to delivering accurate results, the search engines were also very susceptible to spam (spamming of search engines being a practice whereby people would try and cheat the algorythms and have their sites listed in irrelevant places to improve their traffic) and so it was difficult, at best, to actually find anything.
There were ways around these problems. Some sites used the mythical [url=http://www.addedbytes.com/SEO/META_Tags]META tags[/url] (tags used to describe a page's content) to describe each page of a site, and knew which engines to submit a site to, and how to go about it. They knew what the search engines liked to see on a page and what helped a page to rank well for a certain keyword or keyphrase. These people were, and still are, search engine optimizers, people who can turn a nice looking site into an actual income-generator.
SEO itself is about bringing in a decent quantity of quality traffic to a site. Many SEOs sell their services based upon volumes of visitors, and try to drag as many people as possible to a site, whether or not that person is actually interested. Some, usually the better ones, drag as many people as possible to a site, but qualify them first. There is little point in having (and paying for) large volumes of traffic if that traffic is made up of people who are not interested in your product or services.
SEOs also usually handle PPC (pay per click) campaigns. These are quite intimidating to the average web designer, but not for any good reason. Running a good PPC campaign is often a matter of planning and practice, and trying to ensure that the clicks you pay for a worth your while. Again, many SEOs will run a PPC campaign without any serious thought for the return on an investment made, while the successful ones will ensure that more is made from the visitors arriving than is spent on getting them there in the first place (one of the reasons so many dotcoms collapsed in the late 90s was the lack of thought that went into promotion and marketting - people were sometimes paying £50 per visitor to their site and making an average of £10 for each of them - not the best use of capital).
Optimizing your sites for the search engines is, with all this in mind, basically a five stage process: Preparation, Modification, Submission, Campaigning and Maintenance.
If you dive into SEO without a thought of planning, you are unlikely to do well. Things to think of though, before you get started, are who your target audience are and how to reach them. If you sell industrial vibrators, for example, you would do very badly if you decided to target the keyword "vibrators" by itself. Try to put yourself in the shoes of your user. Think what age group they are in, and why your product might appeal to them. Planning well can help you to avoid spending your time and money chasing users who are no use to you, even if they do visit your site.
Once you are happy you have your target audience in mind and have planned your SEO work, then it is time to look at your site. It is important to ensure that a search engine spider can index your site, and that you have included appropriate META tags. It is also essential to ensure that your page titles are well formed and descriptive.
If you have frames, I would suggest removing them. Remember that a visitor can land on any page of your website, completely at random, and if they don't see navigation, they may well just leave. In the same vein, try to imagine how a user would react to landing on each page of your site and think about things that might help that user progress from there to the areas of your site where they can bring in some income for you.
Once your site is up to scratch, you can start the submission process. Ignore anyone who tells you they will submit to anything above about 50 search engines, or that they can guarantee a high placement in any engine - SEO just doesn't work like that. Instead, start by building up links to your site from complimentary resources, and getting listed in the major directories. Once that is done, the spiders will find your site. Then, just keep on building in-bound links and improving your content. The rest will just start to fall into place.
If you offering a product, it might be worth advertising on a pay-per-click basis. There are tonnes of PPC companies around, and plenty of choice out there, but it is worth remembering that cheap isn't necessarily a good thing. However cheap a PPC campaign is, it is useless if you end up without a profit, so when working on PPC, be sure that, above all else, you are working with a reputable company, that can turn you a profit. It might even be worth hiring someone to start your PPC for you, and you never know - they might even be willing you train you to manage it yourself later.
Once you've attained a high ranking, it is very easy to sit back and relax. Much like planning though, maintenance is an important part of SEO. You must keep building up in-bound links, and content on a site. Apart from keeping it fresh for the visitors, this will keep the search engines indexing your site, and every article or page on your site is a potential landing point, and should be able to bring in a little extra traffic, which all mounts over time.
If you have a good business head about you, try and keep an eye on the major search engines and work out what they want to show their visitors. If the most popular engine of the day is showing articles above all else, try and add more articles to your site. If that engine is showing sites without META tags, remove yours. Keeping an eye on the search engines, and thinking of them as businesses, may be one thing that helps you to stay ahead of your competition, which is, after all, the aim of the game.
Do remember that there is more to a web site than traffic. You may be thinking that SEO is the only way you can make more from your site - that numbers equal profit. That is sometimes true, but look at other aspects of your site before jumping in the deep end - can you improve your conversion ratio (the number of people who buy products compared to the number of visitors), or can you make your site more usable? Are you targetting the right audience, or will offline advertising help? Is traditional PR important? Are your potential clients or customers online at all?
Last, but definitely not least - have patience. Improving traffic to a site takes months, and a lot of hard work, and does not always have the effect you desire. It is not a quick or easy process, and should not be undertaken lightly. Most people do not have the time or patience to do their own SEO, and of those that do, many fail because of bad planning, or competing for heavily competitive keywords.
That said, try not to be too put off - doing your own promotion can, if it works, be very rewarding, and not just financially.