Keyword research is the first step you need to do when planning a search engine optimization strategy. Without knowing which words are popular in your content category, your efforts may go unnoticed, or with little reward. Search engine optimization takes months before you start to see results, and if you don't do the proper keyword research, you may end up having wasted your time and effort.
The most popular tool which tells you how many times a search was done is the Overture Keyword Suggestion tool, found at: http://inventory.overture.com/d/searchinventory/suggestion/ . Overture is a pay-per-click (PPC) search engine, where people bid on search result placements. Basically, they are paying for the high rankings in this search engine model. However, they provide the Keyword Suggestion tool for free to anyone. Basically what this tool does is gives you a report of how many times a specific keyword (and related phrases) were searched in their search engine for the previous month. For example, if you type in "Search Engine Optimization", you will see as of 03/14/04, it was searched for 67,741 times in the previous month. The next phrase in the list, which is suggested by the tool is "search engine optimization services" - searched for only 7,261 times in the last month.
Use this tool as a "best guess" estimate of the frequency of other search engines. Google and others don't provide this kind of customized keyword suggestion. Google however does provide a "Top 100+" lists though (link here), but they are only the top 100 words searched for in Google. AltaVista has a similar list (link here). These lists are only good if you're going after those keyword markets.
One thing to keep in mind is that the more times a phrase is searched, the higher the competition will be in obtaining top rankings for those phrases. The Overture Suggestion tool is nice because it suggest alternatives, which can be less competitive (thus, easier to obtain high rankings), and still provide you with plenty of keywords to optimize for. Google Adwords has a similar suggestion tool, although it doesn't give you frequency of how many times the phrase was used (link here).
Keyword Density Analysis (KWDA) refers to an automated way to count the frequency of words and/or phrases on your web page. There are several automated tools which do this, and they all work pretty much the same way (link here). You should at least be able to specify the maximum number of words in a phrase - For example counting all phrases up to 4 words would work for phrases such as "search engine", "search engine optimization", and "search engine optimization info". The Keyword Density Analysis tool would count the frequency of all the word(s) starting with single words, and then two-word phrases, on up to four-word phrases. This will give you a good idea of which keywords you need to use when optimizing your existing pages - not everyone is going to rewrite their site's content in an effort to optimize. Some simple things you can do already existing pages will take your search engine ranking to the next level (See Chapter 4: whatever).